2-Distance vertex-distinguishing index of subcubic graphs | Journal of Combinatorial Optimization Skip to main content
Springer Nature Link
Log in

2-Distance vertex-distinguishing index of subcubic graphs

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

A 2-distance vertex-distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices at distance 2 have distinct sets of colors. The 2-distance vertex-distinguishing index \(\chi ^{\prime }_{\mathrm{d2}}(G)\) of G is the minimum number of colors needed for a 2-distance vertex-distinguishing edge coloring of G. Some network problems can be converted to the 2-distance vertex-distinguishing edge coloring of graphs. It is proved in this paper that if G is a subcubic graph, then \(\chi ^{\prime }_{\mathrm{d2}}(G)\le 6\). Since the Peterson graph P satisfies \(\chi ^{\prime }_{\mathrm{d2}}(P)=5\), our solution is within one color from optimal.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Aigner M, Triesch E (1990) Irregular assignments of trees and forests. SIAM J Discrete Math 3:439–449

    Article  MathSciNet  MATH  Google Scholar 

  • Akbari S, Bidkhori H, Nosrati N (2006) \(r\)-Strong edge colorings of graphs. Discrete Math 306:3005–3010

    Article  MathSciNet  MATH  Google Scholar 

  • Balister PN, Győri E, Lehel J, Schelp RH (2007) Adjacent vertex distinguishing edge-colorings. SIAM J Discrete Math 21:237–250

    Article  MathSciNet  MATH  Google Scholar 

  • Balister PN, Bollobás B, Schelpa RH (2002) Vertex distinguishing colorings of graphs with \(\Delta (G)=2\). Discrete Math 252:17–29

    Article  MathSciNet  MATH  Google Scholar 

  • Bazgan C, Harkat-Benhamdine A, Li H, Woźniak M (1999) On the vertex-distinguishing proper edge-colorings of graphs. J Comb Theoey Ser B 75:288–301

    Article  MathSciNet  MATH  Google Scholar 

  • Bezegová L, Lužar B, Mockovčiaková M, Soták R, Škrekovski R (2016) Star edge coloring of some classes of graphs. J Graph Theory 81:73–82

    Article  MathSciNet  MATH  Google Scholar 

  • Brooks LR (1941) On colouring the nodes of a network. Proc Camb Philos Soc 37:194–197

    Article  MathSciNet  MATH  Google Scholar 

  • Burris AC (1993) Vertex-distinguishing edge-colorings. Ph.D. Dissertation, Memphis State University

  • Burris AC, Schelp RH (1997) Vertex-distinguishing proper edge-colorings. J Graph Theory 26:73–83

    Article  MathSciNet  MATH  Google Scholar 

  • Dvořák Z, Mohar B, Šámal R (2013) Star chromatic index. J Graph Theory 72:313–326

    Article  MathSciNet  MATH  Google Scholar 

  • Hatami H (2005) \(\Delta \)+300 is a bound on the the adjacent vertex distinguishing edge chromatic number. J Comb Theory Ser B 95:246–256

    Article  MathSciNet  MATH  Google Scholar 

  • Huang D, Lih KW, Wang W (2015) Legally \((\Delta +2)\)-coloring bipartite outerplanar graphs in cubic time. Comb Optim Appl, 617–632. Lecture Notes in Comput Sci 9486, Springer, Cham, 2015

  • Petersen J (1891) Die Theorie ser regulären Graphsn. Acta Math 15:193–220

    Article  MathSciNet  Google Scholar 

  • Vučković B (2017) Edge-partitions of graphs and their neighbor-distinguishing index. Discrete Math 340:3092–3096

    Article  MathSciNet  MATH  Google Scholar 

  • Wang W, Huang D, Wang Y, Wang Y, Du DZ (2016) A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs. J Glob Optim 65:351–367

    Article  MathSciNet  MATH  Google Scholar 

  • Wang W, Wang Y, Huang D, Wang Y (2016) 2-Distance vertex-distinguishing edge coloring of graphs (submitted)

  • Wang Y, Wang W, Huo J (2015) Some bounds on the neighbor-distinguishing index of graphs. Discrete Math 338:2006–2013

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang Z, Li J, Chen X, Cheng H, Yao B (2006) \(D(\beta )\)-vertex-distinguishing proper edge-coloring of graphs. Acta Math Sin (Chin Ser) 49:703–708

    MathSciNet  MATH  Google Scholar 

  • Zhang Z, Liu L, Wang J (2002) Adjacent strong edge coloring of graphs. Appl Math Lett 15:623–626

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, China

    Victor Loumngam Kamga, Weifan Wang, Ying Wang & Min Chen

Authors
  1. Victor Loumngam Kamga
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Weifan Wang
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Ying Wang
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Min Chen
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Weifan Wang.

Additional information

Weifan Wang: Research supported by NSFC (No. 11771402);

Min Chen: Research supported by NSFC (Nos. 11471293, 11671053).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Loumngam Kamga, V., Wang, W., Wang, Y. et al. 2-Distance vertex-distinguishing index of subcubic graphs. J Comb Optim 36, 108–120 (2018). https://doi.org/10.1007/s10878-018-0288-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-018-0288-4

Keywords