Name
Abstract | ||
|---|---|---|
The sequential coloring method colors the vertices of a graph in a given order assigning each vertex the smallest available color. A sequential coloring is called connected-coloring if at any time the colored vertices induce a connected graph. A graph G is said to be hard-to-color if every connected-coloring produces a nonoptimal coloring and partially hard-to-color if every such coloring starting in a specified vertex v is nonoptimal. We present smallest partially hard- to-color graphs. Further a hard-to-color graph with 18 vertices is stated which is believed to be the smallest graph with this property. We prove that it is the smallest cubic hard-to-color graph. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0166-218X(94)90090-6 | Discrete Applied Mathematics |
Keywords | Field | DocType |
connected sequential colorings,hard-to-color graph | Edge coloring,Discrete mathematics,Complete coloring,Combinatorics,Graph power,Fractional coloring,List coloring,Cycle graph,Greedy coloring,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
51 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
3 | 0.70 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luitpold Babel | 1 | 182 | 22.84 |
| Gottfried Tinhofer | 2 | 112 | 20.81 |