Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs

R. R. Kamalian

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2014), pp. 3-12.

Résumé

For an undirected, simple, finite, connected graph $G$, we denote by $V(G)$ and $E(G)$ the sets of its vertices and edges, respectively. A function $\phi :E(G)\to \{1,2,\dots ,t\}$ is called a proper edge $t$-coloring of a graph $G$ if all colors are used and no two adjacent edges receive the same color. An arbitrary nonempty subset of consecutive integers is called an interval. The set of all proper edge $t$-colorings of $G$ is denoted by $\alpha (G,t)$. The minimum value of $t$ for which there exists a proper edge $t$-coloring of a graph $G$ is denoted by ${\chi }^{\prime }(G)$. Let $$ \alpha(G)\equiv\bigcup_{t=\chi'(G)}^{|E(G)|}\alpha(G,t). $$ If $G$ is a graph, $\phi \in \alpha (G)$, $x\in V(G)$, then the set of colors of edges of $G$ incident with $x$ is called a spectrum of the vertex $x$ in the coloring $\phi$ of the graph $G$ and is denoted by $S_G(x,\phi )$. If $\phi \in \alpha (G)$ and $x\in V(G)$, then we say that $\phi$ is interval (persistent-interval) for $x$ if $S_G(x,\phi )$ is an interval (an interval with 1 as its minimum element). For an arbitrary graph $G$ and any $\phi \in \alpha (G)$, we denote by $f_{G,i}(\phi )(f_{G,pi}(\phi ))$ the number of vertices of the graph $G$ for which $\phi$ is interval (persistent-interval). For any graph $G$, let us set $$ \eta_i(G)\equiv\max_{\varphi\in\alpha(G)}f_{G,i}(\varphi),\quad\eta_{pi}(G)\equiv\max_{\varphi\in\alpha(G)}f_{G,pi}(\varphi). $$ For graphs $G$ from some classes of graphs, we obtain lower bounds for the parameters ${\eta }_i(G)$ and ${\eta }_{pi}(G)$.

Bibliographie

[1] Asratian A. S., Investigation of some mathematical model of Scheduling Theory, Doctoral dissertation, Moscow University, 1980 (in Russian)

[2] Asratian A. S., Casselgren C. J., A sufficient condition for interval edge colorings of $(4,3)$-biregular bipartite graphs, Research report LiTH-MAT-R-2006-07, Linköping University, 2006

[3] Asratian A. S., Casselgren C. J., Some results on interval edge colorings of $(\alpha,\beta)$-biregular bipartite graphs, Research report LiTH-MAT-R-2006-09, Linköping University, 2006

[4] Asratian A. S., Casselgren C. J., “On interval edge colorings of $(\alpha,\beta)$-biregular bipartite graphs”, Discrete Math., 307 (2007), 1951–1956 | DOI | MR | Zbl

[5] Asratian A. S., Casselgren C. J., Vandenbussche J., West D. B., “Proper path-factors and interval edge-coloring of $(3,4)$-biregular bigraphs”, J. of Graph Theory, 61 (2009), 88–97 | DOI | MR | Zbl

[6] Asratian A. S., Kamalian R. R., “Interval colorings of edges of a multigraph”, Appl. Math. (Yerevan), 1987, no. 5, 25–34 (in Russian) | MR

[7] Asratian A. S., Kamalian R. R., “Investigation of interval edge-colorings of graphs”, Journal of Combinatorial Theory, Series B, 62:1 (1994), 34–43 | DOI | MR | Zbl

[8] Caro Y., Schönheim J., “Generalized $1$-factorization of trees”, Discrete Math., 33 (1981), 319–321 | DOI | MR | Zbl

[9] Giaro K., “The complexity of consecutive $\Delta$-coloring of bipartite graphs: 4 is easy, 5 is hard”, Ars Combin., 47 (1997), 287–298 | MR | Zbl

[10] Giaro K., Compact Task Scheduling on Dedicated Processors with no Waiting Periods, Ph. D. Thesis, Technical University of Gdańsk, ETI Faculty, Gdańsk, 1999 (in Polish)

[11] Giaro K., Kubale M., Małafiejski M., “Compact scheduling in open shop with zero-one time operations”, INFOR, 37:1 (1999), 37–47

[12] Hansen H., Scheduling with minimum waiting periods, Master Thesis, Odense University, Odense, Denmark, 1992 (in Danish)

[13] Hanson D., Loten C. O. M., “A lower bound for Interval colouring bi-regular bipartite graphs”, Bulletin of the ICA, 18 (1996), 69–74 | MR | Zbl

[14] Hanson D., Loten C. O. M., Toft B., “On interval colourings of bi-regular bipartite graphs”, Ars Combin., 50 (1998), 23–32 | MR | Zbl

[15] Holyer I., “The $NP$-completeness of edge-coloring”, SIAM J. Comput., 10 (1981), 718–720 | DOI | MR | Zbl

[16] Kamalian R. R., Interval Edge Colorings of Graphs, Doctoral dissertation, the Institute of Mathematics of the Siberian Branch of the Academy of Sciences of USSR, Novosibirsk, 1990 (in Russian)

[17] Kamalian R. R., On a number of vertices with an interval spectrum in proper edge colorings of some graphs, Research report LiTH-MAT-R-2011/03-SE, Linköping University, 2011

[18] Kostochka A. V., Unpublished manuscript, 1995

[19] Leven D., Galil Z., “$NP$-completeness of finding the chromatic index of regular graphs”, J. Algorithms, 4 (1983), 35–44 | DOI | MR | Zbl

[20] Pyatkin A. V., “Interval coloring of $(3,4)$-biregular bipartite graphs having large cubic subgraphs”, J. of Graph Theory, 47 (2004), 122–128 | DOI | MR | Zbl

[21] Sevast'janov S. V., “Interval colorability of the edges of a bipartite graph”, Metody Diskret. Analiza, 50 (1990), 61–72 (in Russian) | MR

[22] Vizing V. G., “The chromatic index of a multigraph”, Kibernetika, 3 (1965), 29–39 | MR | Zbl

[23] West D. B., Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996 | MR | Zbl