《图论》课程教学资源（书籍文献）Color-Induced Graph Colorings

Contents 1 Introduction...... 1.1 The Origin of Edge Colorings........................ 1.2 Proper Edge Colorings.... 2 1.3 Proper Vertex Colorings 3 2 The Irregularity Strength of a Graph 5 2.1 Defined ity Strength. 2.2 nregularity Strength of Paths and Cycles 1 2.4 Additional Bounds for the Irregularity Strength of a Graph.......... 2 3 Modular Sum-Defined Irregular Colorings................ 3.1 Graceful Graphs..... 5 3.2 Modular Edge-Graceful Graphs 3.3 Non-modular Edge-Graceful Graphs 3.4 Nowhere-Zero Modular Edge-Gra ceful Graphs 40 4 Set-Defined Irregular Colorings 4.1 The Set Irregular Chromatic Index........... 4.2 Complete Graphs and Hypercubes. 4.3 Complete Bipartite Graphs. 49 5 Multiset-Defined Irregular Colorings 5.1 The Multiset Irregular Chromatic Index....... 少 5.2 Regular Graphs 530 omplete Bipartite Graphs t44t4小t4ttt44tte 55 Max-Min Value Problcms 00t。tttt0t4e000。tet。0t。tt500tttt。t0t。ttt。tt0t+。 5638 6 Sum-Defined Neighbor-Distinguishing Colorings........................ 0 6.1 The Sum Distinguishing Index....................... 6.2 The 1-2-3 Conjecture.. 63 6.3 The Multiset Distinguishing Index........ xi

Contents 1 Introduction .................................................................. 1 1.1 The Origin of Edge Colorings .......................................... 1 1.2 Proper Edge Colorings.................................................. 2 1.3 Proper Vertex Colorings ................................................ 3 2 The Irregularity Strength of a Graph ..................................... 5 2.1 Sum-Defined Vertex Colorings: Irregularity Strength ................. 5 2.2 On the Irregularity Strength of Regular Graphs ....................... 8 2.3 The Irregularity Strength of Paths and Cycles ......................... 17 2.4 Additional Bounds for the Irregularity Strength of a Graph .......... 22 3 Modular Sum-Defined Irregular Colorings............................... 31 3.1 Graceful Graphs......................................................... 32 3.2 Modular Edge-Graceful Graphs ........................................ 33 3.3 Non-modular Edge-Graceful Graphs................................... 37 3.4 Nowhere-Zero Modular Edge-Graceful Graphs ....................... 40 4 Set-Defined Irregular Colorings............................................ 43 4.1 The Set Irregular Chromatic Index ..................................... 43 4.2 Complete Graphs and Hypercubes ..................................... 45 4.3 Complete Bipartite Graphs ............................................. 49 5 Multiset-Defined Irregular Colorings...................................... 51 5.1 The Multiset Irregular Chromatic Index ............................... 51 5.2 Regular Graphs.......................................................... 54 5.3 Complete Bipartite Graphs ............................................. 55 5.4 Trees ..................................................................... 56 5.5 Max-Min Value Problems .............................................. 58 6 Sum-Defined Neighbor-Distinguishing Colorings ........................ 61 6.1 The Sum Distinguishing Index ......................................... 61 6.2 The 1-2-3 Conjecture ................................................... 63 6.3 The Multiset Distinguishing Index ..................................... 65 xi

xii Contents 69 21 7.2 Bipartite Graphs........ 7.3 Modular Chromatic Index and Chromatic Number................... 个 8 Strong Edge Colorings of Graphs. 8.1 The Strong Chromatic Index 81 8.2 Binomial Colorings of Graphs 8.3 The Neighbor Strong Chromatic Index. 91 9 Sum-Defined Chromatic Indices 91 The Irregular-Sum Chromatic Index 9.2 The Proper-Sum Chromatic Index .................. 9.3 The Twin Chromatic Index...................... 102 4 Trees.................................................................... 106 References.... 113 117

xii Contents 7 Modular Sum-Defined Neighbor-Distinguishing Colorings ............. 69 7.1 Modular Chromatic Index .............................................. 69 7.2 Bipartite Graphs......................................................... 71 7.3 Modular Chromatic Index and Chromatic Number ................... 77 8 Strong Edge Colorings of Graphs.......................................... 81 8.1 The Strong Chromatic Index ........................................... 81 8.2 Binomial Colorings of Graphs ......................................... 85 8.3 The Neighbor Strong Chromatic Index ................................ 91 9 Sum-Defined Chromatic Indices ........................................... 95 9.1 The Irregular-Sum Chromatic Index ................................... 95 9.2 The Proper-Sum Chromatic Index ..................................... 98 9.3 The Twin Chromatic Index ............................................. 102 9.4 Trees ..................................................................... 106 References......................................................................... 113 Index ............................................................................... 117

List of Figures Fig.2.1 Showing s(K3)=3.. 1 Fig.2.2 An edge coloring of the Petersen graph............................. 9 Fig.2.3 An edge coloring of K4...... 12 Fig.2.4 An edge coloring of Ka Fig.2.5 Constructing the graph H inK 公 g2.6 the proof of for 044.444.4444444.4“444444。小。 Fig.2.7 Edge cole 0ngs0 f Co and C13....... Fig.2.8 Edge c0l0mngs0fC10andC12.......................... 19201 Fig.2.9 Edge colorings of C and Cu.................. Fig.2.10 Illustrating that the inequality in Proposition 2.14 can be strict.... Fig.2.11 Illustrating the equality in Proposition 2.14........ 23 Fig.2.12 An edge coloring of the tree T Fig.2.13 An edge coloring graph 21 Fg2.14 An edge coloring of a connected graph of Fig.3.1 Illustrating B-valuations of C3 and C.. 32 Fig.3.2 Three graphs that are not graceful..... Fig.3.3 Two modular edge-graceful graphs and a non-modular edge-graceful graph........ Fig.3.4 Two modular edge-graceful trees... Fig.3.5 The colorings in Subease 2.I fors3 ands7. 34 Fig.3.6 Two modular edge-graceful colorings of a graph.. 号 The graph set irregular chromatic index Set irregular edge colorings of K and K....... Fig.4.3 A set irregular 4-edge coloring of Ks.. Fig.4.4 A set irregular 3-edge coloring of 2=C4......................... 41

List of Figures Fig. 2.1 Showing s.K3/ D 3 ................................................... 7 Fig. 2.2 An edge coloring of the Petersen graph ............................. 9 Fig. 2.3 An edge coloring of K4;4 ............................................. 12 Fig. 2.4 An edge coloring of K5;5 ............................................. 14 Fig. 2.5 Constructing the graph H in K3.4/ .................................... 15 Fig. 2.6 Edge colorings of Pn in the proof of Theorem 2.12 for 19 Fig. 2.7 Edge colorings of C9 and C13 ........................................ 20 Fig. 2.8 Edge colorings of C10 and C12 ....................................... 21 Fig. 2.9 Edge colorings of C7 and C11 ........................................ 22 Fig. 2.10 Illustrating that the inequality in Proposition 2.14 can be strict .... 23 Fig. 2.11 Illustrating the equality in Proposition 2.14 ......................... 23 Fig. 2.12 An edge coloring of the tree T2 ...................................... 25 Fig. 2.13 An edge coloring of a unicyclic graph G ........................... 27 Fig. 2.14 An edge coloring of a connected graph of size n C 1 .............. 28 Fig. 3.1 Illustrating ˇ-valuations of C3 and C4 ............................... 32 Fig. 3.2 Three graphs that are not graceful ................................... 32 Fig. 3.3 Two modular edge-graceful graphs and a non-modular edge-graceful graph................................................... 33 Fig. 3.4 Two modular edge-graceful trees .................................... 34 Fig. 3.5 The colorings in Subcase 2:1 for s D 3 and s D 7 .................. 39 Fig. 3.6 Two modular edge-graceful colorings of a graph ................... 41 Fig. 4.1 The graph G7 of order 7 with set irregular chromatic index 3 ...... 44 Fig. 4.2 Set irregular edge colorings of K3 and K4 ........................... 46 Fig. 4.3 A set irregular 4-edge coloring of K8 ................................ 46 Fig. 4.4 A set irregular 3-edge coloring of Q2 D C4 ......................... 47 xiii 6 n 10 ............................................................ 19

xiv List of Figures Fig.4.5 a set irregular dge coloring of 4....... 48 Fig.4.6 Showing that si(K2.2)=3 and si(K33)=si(K4.4)=4............ 49 Fig.5.1 A multiset irregular 2-edge coloring.. 52 Fig.5.2 Showing that s(Ps)=3 and mi(Ps)=2.... 2 Fig.5.3 Multiset irregular edge colorings of connected graphs of order 4 Fig.5.4 Fig.6.1 Minimum prope 62 Fig.6.2 a proper sum edge coloring........ Fig.7.1 A modular 3-edge coloring of a graph........... Fig.7.2 A modular 3-edge coloring of the Petersen graph. 10 Fig.8.1 A strong 5-edge coloring of a graph.... Fig.8.2 s of order 7 with st g.&3 The tre romatic index order 15 with ong c omatic index 4... u graphs for k 8 Fig.8.5 Four proper binomial-colored graphs 86 Fig.8.6 A labeled proper 3-binomial-colored graph Fig.8.7 Illustrating a step of the proof of Theorem 8.5................ 导 Fig.8.8 Illustrating the coloring c in the proof of Theorem 8.6 fork4 Fig.8.9 A graph G with (G)=4.. A graph G with xi(G)=5. A graph G with A twin edge 4 900 F1g.9.4 Illustrating Mo.M1.M2.M3 and F1.F2.F3.F for K8............... 5 Fig.9.5 A twin edge 7-coloring of S5.5....................................11

xiv List of Figures Fig. 4.5 Constructing a set irregular 4-edge coloring of Q3 and a set irregular 5-edge coloring of Q4 ................................. 48 Fig. 4.6 Showing that si.K2;2/ D 3 and si.K3;3/ D si.K4;4/ D 4 ............ 49 Fig. 5.1 A multiset irregular 2-edge coloring ................................. 52 Fig. 5.2 Showing that s.P5/ D 3 and mi.P5/ D 2 ............................ 52 Fig. 5.3 Multiset irregular edge colorings of connected graphs of order 4 .............................................................. 53 Fig. 5.4 A step in the proof of Theorem 5.8 .................................. 56 Fig. 6.1 Minimum proper sum colorings of graphs .......................... 62 Fig. 6.2 A multiset neighbor-distinguishing of a tree that is not a proper sum edge coloring........................................... 65 Fig. 7.1 A modular 3-edge coloring of a graph ............................... 70 Fig. 7.2 A modular 3-edge coloring of the Petersen graph................... 70 Fig. 8.1 A strong 5-edge coloring of a graph ................................. 82 Fig. 8.2 The trees of order 7 with strong chromatic index 3 ................. 83 Fig. 8.3 A graph of order 15 with strong chromatic index 4 ................. 83 Fig. 8.4 The k-binomial graphs for k D 2; 3 .................................. 86 Fig. 8.5 Four proper binomial-colored graphs................................ 86 Fig. 8.6 A labeled proper 3-binomial-colored graph ........................ 87 Fig. 8.7 Illustrating a step of the proof of Theorem 8.5 ...................... 88 Fig. 8.8 Illustrating the coloring c in the proof of Theorem 8.6 for k D 4 .............................................................. 90 Fig. 8.9 A graph G with 0 ns.G/ D 4 .......................................... 91 Fig. 9.1 A graph G with 0 is.G/ D 5 .......................................... 96 Fig. 9.2 A graph G with 0 ps.G/ D 4 .......................................... 99 Fig. 9.3 A twin edge 4-coloring of the Petersen graph ....................... 102 Fig. 9.4 Illustrating M0; M1; M2; M3 and F1; F2; F3; F4 for K8 ............... 105 Fig. 9.5 A twin edge 7-coloring of S5;5 ....................................... 111

Chapter 1 Introduction One of the most popular areas of study in graph theory is colorings.This topic can be traced back to the origin of the Four Color Problen and whether it is possible to color the egions of every map with four or fewe two regions having a common b Later it was seen that this problem could be looked at as a problem in graph theory- whethe it is always possible to color the regions of every planar graph (embedded in the plane)so that every two adjacent regions are colored differently.It became known that the Four Color Problem could be solved if it could be solved for all bridgeless cubic planar graphs. 1.1 The Origin of Edge Colorings The Scottish mathematician Tait [76]discovered a unique approach to solve the Four Color Problem.He proved that the edges of a bridgeless cubic planar graph G can be colored with three colors so that every two adjacent edges are colored differently if and only if the regions of G can be colored with four colors so that every two adjacent eareiferey Although Tait's approach ever edtoa solution of the Four Color Problem,he such a 3-coloring of p jo AltEAsps s of G induce an approp e ns of G.The al of induce,in a number of ways,vertex colorings possessing desirable properties. Colors can be objects of any type.While initially,the colors that were used to color the regions of maps were actual colors such as red,blue,green and so on,later it became common to use positive integers for colors as these were simpler and it was easier to keep track of the number of colors being used.Later yet,elements of Zk.the integers modulo k,for somek2.were sometimes used as colors.Subsets or multisets of some set were also used as c lors.Originally,the only requirem Ping Zhang 2015 orings.SpringerBriefs in Mathematics

Chapter 1 Introduction One of the most popular areas of study in graph theory is colorings. This topic can be traced back to the origin of the Four Color Problem and whether it is possible to color the regions of every map with four or fewer colors in such a way that every two regions having a common boundary are assigned different colors. Later it was seen that this problem could be looked at as a problem in graph theory—whether it is always possible to color the regions of every planar graph (embedded in the plane) so that every two adjacent regions are colored differently. It became known that the Four Color Problem could be solved if it could be solved for all bridgeless cubic planar graphs. 1.1 The Origin of Edge Colorings The Scottish mathematician Tait [76] discovered a unique approach to solve the Four Color Problem. He proved that the edges of a bridgeless cubic planar graph G can be colored with three colors so that every two adjacent edges are colored differently if and only if the regions of G can be colored with four colors so that every two adjacent regions are colored differently. Although Tait’s approach never led to a solution of the Four Color Problem, he was able to prove that such a 3-coloring of the edges of G induce an appropriate 4-coloring of the regions of G. The goal of this book is to describe a variety of edge colorings that have been introduced which induce, in a number of ways, vertex colorings possessing desirable properties. Colors can be objects of any type. While initially, the colors that were used to color the regions of maps were actual colors such as red, blue, green and so on, later it became common to use positive integers for colors as these were simpler and it was easier to keep track of the number of colors being used. Later yet, elements of Zk, the integers modulo k, for some k 2, were sometimes used as colors. Subsets or multisets of some set were also used as colors. Originally, the only requirement © Ping Zhang 2015 P. Zhang, Color-Induced Graph Colorings, SpringerBriefs in Mathematics, DOI 10.1007/978-3-319-20394-2_1 1