Revision #156 → #1270 · back to history
addedGraph coloringcece67ca531d
addedFive color theorem48c9044a0e36
addedProper vertex coloring25fca6255515
addedk-coloring443029c328cb
addedChromatic numberc63f5c47f349
addedk-colorable and k-chromaticaedb98663c66
addedColor class5a227f228f9e
addedk-coloring as partition into independent sets7aee2761e7b5
addedThree-coloring count example51754cec368a
addedChromatic polynomial51e30806baf4
addedChromatic number from chromatic polynomial4741095b7ba0
addedEdge coloring70eb5f006e41
addedk-edge-coloring3196c1abb6d2
addedChromatic index60d729a4390f
addedTait coloringe45bb34c95cd
addedFour color theorem via Tait coloring508fa67e9253
addedTotal coloringceecb15ab345
addedTotal chromatic numberf0191e2b72d4
addedFace coloring564081fec71b
addedTutte's flow theorem4841240c5f81
addedUnlabeled coloringf1e270ad4364
addedUnlabeled chromatic polynomial analogue2efb93e6b2b5
addedTrivial upper bound χ ≤ naacf2c5e6427
added1-colorable graphs are edgeless69a9b4f7c0e0
addedComplete graph chromatic numberaa3ec9ea0519
addedLower bound from edgesb187b21b3972
addedχ-bounded familya42d51a48c73
addedPerfect graphs χ-bounded by clique numbereb7f1e1c64a1
added2-colorable graphs are bipartitec0424d2c9023
addedPlanar graphs are 4-colorableaee407c0efb6
addedGreedy bound χ ≤ Δ+17d45d00a3a2a
addedΔ+1 bound tight for complete graphs and odd cyclese092e3b112a2
addedBrooks' theoremae304a10c449
addedClique number lower boundb0ceb2fe33d2
addedClique bound tight for perfect graphseec5cab6d4cb
addedHoffman's bound778c30890c86
addedVector chromatic number bound63e6d9c4cc71
addedLovász number lower boundb9bbd34a2b85
addedFractional chromatic number lower bound728f8253c7af
addedOrdering of the lower bounds990259e7f787
addedLarge cliques imply high χ, not converselyee65463de589
addedGrötzsch graph9b082b040fda
addedTriangle-free graphs of arbitrarily high χ0d689edab1e7
addedBurling graphsc9c54747227a
addedBoxes and segments not χ-bounded868e8f44fb40
addedHigh χ requires high maximum degree1a7605258def
addedErdős: high girth and high χd82b38150232
addedEdge coloring = vertex coloring of line graphd1f6a101851c
addedChromatic index at least max degreeb9ccf70a6482
addedKőnig's theorem4fcd9683e1ab
addedVizing's theoremf67696ac2c26
addedGallai–Hasse–Roy–Vitaver theorem95eaa463cc63
addedPlanar colorings dual to nowhere-zero flowsc5231a19d480
addedde Bruijn–Erdős theorem91797cc0c938
addedFawcett's infinite full coloring theorem2a9af3319b02
addedReed's conjecturec8da4e9c654f
addedChromatic number of the plane2e4588b2f93c
addedHadwiger, Erdős–Faber–Lovász, Albertson conjectures93dead64e0cf
addedBirkhoff–Lewis conjecturefb16c7aa82eb
addedChromatic polynomial characterization problemsd9d8a3a9ea7d
added2-coloring = bipartiteness in linear timee9bd5e8ef243
addedPerfect graphs colorable in polynomial time52761eefe1ff
addedClosed-form chromatic polynomials66f3786ad5d8
addedLow branch-width polynomial time5064f190c246
addedBrute-force coloring search4c4cc3d06a62
addedDynamic programming colorability boundb05cec2c5000
addedInclusion–exclusion colorability bound713b59124152
addedFaster 3- and 4-colorability algorithms56773d8e92cb
addedFaster 5- and 6-colorability algorithmscb49ddba5707
addedContraction of a graphd19853915acf
addedChromatic number recurrence (Zykov)e4f7bbbf4628
addedChromatic polynomial recurrence2b3d91f30c8c
addedDeletion–contraction algorithm21198f7e1342
addedDeletion–contraction running timed7ced65e3c49
addedGreedy coloring algorithm6a9c062383ae
addedOptimal greedy ordering exists06db4a742547
addedCrown graph greedy worst casecc822d5841d3
addedGreedy optimal on chordal graphsd43c2b5f53a7
addedWelsh–Powell degree ordering bounde778bed00125
addedGrundy numberf768f62582e5
addedDSatur and RLF heuristics31a438516089
addedDegree of saturationa1faf9a5ef31
addedRecursive largest first algorithm626b4a95a294
addedDSatur worst-case complexity79ab43e6fd51
addedDSatur and RLF exact on special graphs6d434f2cef29
addedLOCAL model coloring upper bounde385504a85a7
addedLOCAL model matching lower bound3724c4dc7f5f
addedNo deterministic coloring of symmetric graphsdc7393dba75d
addedDistributed greedy needs Θ(n) roundsfc7fce1b1312
addedCole–Vishkin one-step color reductionf568e1ccdf12
addedCole–Vishkin 3-coloring of cycle6a4b115ccf9c
addedLinial's lower bound5a3fa5feadc6
addedPanconesi–Rizzi distributed edge coloringc987b8673615
addedDecentralized coloring existsf05fe4074fdb
addedLearning automata coloring almost surely5b344bbeb004
addedNP-completeness of k-coloring493ad662ef7d
addedNP-hardness of chromatic number058b9c64b95d
added3-coloring NP-complete on 4-regular planar graphs8d2c8125a03c
added3-coloring linear time for max degree 3d78e38a1d12c
addedLexicographically smallest 4-coloring NP-complete5434db9e31ae
addedBest known approximation factore9112538415c
addedHardness of approximating chromatic number0911a3203564
addedHardness of coloring k-colorable graphs850371d85733
addedChromatic polynomial coefficients #P-hardad295b889108
addedEvaluating chromatic polynomial #P-hard0a10be7727cb
addedNo FPRAS for chromatic polynomial8ce12e9dddf9
addedVizing's proof gives Δ+1 edge coloring01b0c7ec508a
addedEdge chromatic number NP-completecc0608db13bd
addedEdge chromatic number 4/3-approximation5052798a35bc
addedChromatic number equals minimum makespan88565d93f79c
addedAircraft scheduling interval graph54aafae9371f
addedBandwidth allocation unit disk graphbe897b507495
addedInterference graphc517100eedae
addedk-coloring gives register assignment782a1791e707
addedTheorem on friends and strangers2414c926ade5
addedModular coloring2a12e48edef2
addedColor sum2d951163553f
addedModular k-coloring6e7b25c5b1c1
addedModular chromatic number9b7403eb1afa
addedModular coloring worked example1cd97467a48a
addedAdjacent-vertex-distinguishing total coloring5f8d3e265a63
addedAcyclic coloring08b1ad15e084
addedb-coloringe827939e0d56
addedBounded coloringd57d265c4fbf
addedCentered coloring083e14968d2f
addedCircular coloringe835dabe5a6c
addedCocoloring7f172a5cc949
addedComplete coloring2aa29c0c8723
addedDefective coloring6f5e8d83573b
addedDistinguishing coloring485b5c0c4c7c
addedEquitable coloringf0c8612351a8
addedExact coloringc97673172462
addedFractional coloring6829fc3397d5
addedDetour-distance coloring460007ad5f2c
addedHarmonious coloring403423d29a02
addedIncidence coloringac4fc92f8e5e
addedKaleidoscopic coloring393b81e48cb8
addedInterval (ordered) coloring05bda78a6f5e
addedInterval edge coloring3982502554b3
addedList coloring5f86b1fa20cb
addedList edge coloringa81f97b216a0
addedL(h,k)-coloringf12f0efc7259
addedOriented coloring1879d263a91f
addedPacking coloring7b881c9d95ba
addedPath coloring577c5b85e6a8
addedRadio coloringe8a018bc3aab
addedRanking (ordered) coloring466cde5f6358
addedSubcoloring4f9823cb2b08
addedSum coloring6d1126ad9745
addedStar coloringfb39d118d739
addedStrong coloringaa04919cb6da
addedStrong edge coloring9c6418809f30
addedT-coloringfd8a20f50aba
addedTotal coloring (list entry)027159bbe91c
addedTriangle-free edge coloringe9ffec63a71e
addedWeak coloring2023849df157
addedColoring of signed and gain graphs1c1e04db4949