On locally irregular decompositions of subcubic graphs

• Autorzy: Baudon O. , Bensmail J. , Hocquard H. , Senhaji M. , Sopena E.

Identyfikatory

DOI

10.7494/OpMath.2018.38.6.795

• Języki publikacji: EN

Abstrakty

EN

A graph G is locally irregular if every two adjacent vertices of G have different degrees. A locally irregular decomposition of G is a partition E1,.. . , Ek of E(G) such that each G[Ei] is locally irregular. Not all graphs admit locally irregular decompositions, but for those who are decomposable, in that sense, it was conjectured by Baudon, Bensmail, Przybyło and Woźniak that they decompose into at most 3 locally irregular graphs. Towards that conjecture, it was recently proved by Bensmail, Merker and Thomassen that every decomposable graph decomposes into at most 328 locally irregular graphs. We here focus on locally irregular decompositions of subcubic graphs, which form an important family of graphs in this context, as all non-decomposable graphs are subcubic. As a main result, we prove that decomposable subcubic graphs decompose into at most 5 locally irregular graphs, and only at most 4 when the maximum average degree is less than 12/5. We then consider weaker decompositions, where subgraphs can also include regular connected components, and prove the relaxations of the conjecture above for subcubic graphs.

Słowa kluczowe

EN

locally irregular edge-colouring irregular chromatic index; subcubic graphs

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2018
• Tom: Vol. 38, no. 6
• Strony: 795--817
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Baudon O.

• Univ. Bordeaux LaBRI, UMR5800, F-33400 Talence, France
• CNRS LaBRI, UMR5800, F-33400 Talence, France

autor

Bensmail J.

• INRIA and Universite Nice-Sophia-Antipolis I3S, UMR 7271, 06900 Sophia-Antipolis, France

autor

Hocquard H.

• Univ. Bordeaux LaBRI, UMR5800, F-33400 Talence, France
• CNRS LaBRI, UMR5800, F-33400 Talence, France

autor

Senhaji M.

• Univ. Bordeaux LaBRI, UMR5800, F-33400 Talence, France
• CNRS LaBRI, UMR5800, F-33400 Talence, France

autor

Sopena E.

• Univ. Bordeaux LaBRI, UMR5800, F-33400 Talence, France
• CNRS LaBRI, UMR5800, F-33400 Talence, France

Bibliografia

• [1] O. Baudon, J. Bensmail, J. Przybyło, M. Woźniak, On decomposing regular graphs into locally irregular subgraphs, European Journal of Combinatorics 49 (2015), 90-104.
• [2] O. Baudon, J. Bensmail, E. Sopena, On the complexity of determining the irregular chromatic index of a graph, Journal of Discrete Algorithms 30 (2015), 113-127.
• [3] J. Bensmail, M. Merker, C. Thomassen, Decomposing graphs into a constant number of locally irregular subgraphs, European Journal of Combinatorics 60 (2017), 124-134.
• [4] J. Bensmail, B. Stevens, Edge-partitioning graphs into regular and locally irregular components, Discrete Mathematics and Theoretical Computer Science 17 (2016) 3, 43-58.
• [5] A. Dehghan, M.-R. Sadeghi, A. Ahadi, Algorithmic complexity of proper labeling problems, Theoretical Computer Science 495 (2013), 25-36.
• [6] M. Karoński, T. Łuczak, A. Thomason, Edge weights and vertex colours, Journal of Combinatorial Theory, Series B 91 (2004), 151-157.
• [7] B. Lużar, J. Przybyło, R. Sotak, New bounds for locally irregular chromatic index of bipartite and subcubic graphs. Preprint arXiv:1611.02341.
• [8] J. Przybyło, On decomposing graphs of large minimum degree into locally irregular subgraphs, Electronic Journal of Combinatorics 23 (2016) 2, #P2.31.
• [9] B. Seamone, The 1-2-3 Conjecture and related problems: a survey, preprint arXiv:1211.5122.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).