StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POGraph theory - chromatic index
text
Body
copied!<p>I have to make a program which will say if graph is d colorable or not - basically i have to check if chromatic index is d or d+1, where d is max degree of all vertices (vizing's theorem). I know this problem is NP-complete and basically it has to be bruteforced. I had an idea but don't know if it is correct - </p> <p>1) find vertex with deg(v) = d and color all edges incident with v with d distnict colors.</p> <p>2) for all edges incident with vertices which are adjacent to v, apply some color from set of d colors</p> <p>3) repeat 2) for "discovered" edges</p> <p>If all edges are colored with d colors, chromatic index is d and i have one coloring of graph G.</p> <p>If some edge can't be colored with color from set of d colors, color him with d+1-st color and color remaining edges with colors from set of d+1 colors - here is the question - using this scheme, if i proclaim that chromatic index to be d+1, is there a chance that with some other coloring chromatic index would be d? (for every edge that is going to be colored I'm choosing one color which can be used)..</p> <p>Also, which graph representation would be best for this problem? In input file graph is written in adjacency matrix. i know it can be solved with recursion, but I don't have an idea how. I'm stuck with some too complicated ideas :S (some hint or pseudocode would be appreciated).</p> <h3>Edit:</h3> <p>Just came across my mind, I think it should be ok (pure bruteforce). I didnt try to implement this yet. Please comment if you see something wrong. Just to say again - algorithm should check whether graph is edge colorable with d or d+1 colors where d is max degree of all vertices in given simple graph, and to find one coloring...</p> <pre><code>colorEdge(edge, color, extra) { if (edge colored) return; //if already colored, return if (can be colored in color) color it; //if color can be applied, apply it else { //else, 'd+1'-st color neded, so color it with that color, continue finding //coloring with d+1 colors extra = true; color it in color extra; } //recursivly try to color adjacent edges with available colors for each color c' from set of d colors { for each edge k adjacent to current { colorE(k, c', extra) } } } //main bool extra = false; for each color b from set of d colors { colorEdge(some starting edge, b, extra) if (!extra) break; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload