11institutetext: SINTEF, Strindvegen 4, 7030 Trondheim, Norway
11email: {rasmus.ulfsnes<EMAIL_ADDRESS>
22institutetext: Department of Informatics, University of Oslo, Oslo, Norway
22email<EMAIL_ADDRESS>
33institutetext: NTNU, Trondheim, Norway
33email<EMAIL_ADDRESS>
# Transforming Software Development with Generative AI: Empirical Insights on
Collaboration and Workflow

Rasmus Ulfsnes 11 0000-1111-2222-3333 Nils Brede Moe 11 0000-0003-2669-0778
Viktoria Stray 1122 0000-0002-6032-2074 Marianne Skarpen 33
0009-0005-5575-316X

###### Abstract

Generative AI (GenAI) has fundamentally changed how knowledge workers, such as
software developers, solve tasks and collaborate to build software products.
Introducing innovative tools like ChatGPT and Copilot has created new
opportunities to assist and augment software developers across various
problems. We conducted an empirical study involving interviews with 13 data
scientists, managers, developers, designers, and frontend developers to
investigate the usage of GenAI. Our study reveals that ChatGPT signifies a
paradigm shift in the workflow of software developers. The technology empowers
developers by enabling them to work more efficiently, speed up the learning
process, and increase motivation by reducing tedious and repetitive tasks.
Moreover, our results indicate a change in teamwork collaboration due to
software engineers using GenAI for help instead of asking co-workers which
impacts the learning loop in agile teams.

###### Keywords:

Agile software development Product development Teamwork.

##  1 Introduction

There is a growing trend among companies to adopt digitalization and engage in
digital transformation[36]. This transformation process requires technologies
as software, data and artificial intelligence [5], forcing a shift in the use
of strategic frameworks [30], and new ways of developing technology for highly
skilled employees with intelligent technology [36].

Technology for assisting developers with writing code, particularly using
Integrated Development Environments (IDEs) is not a new concept [26, 17]. The
task of autocompletion of code, and generating of test, and various other
tasks has been particularly interesting for software, as natural language
matches quite well as the software code is hypothesized to be a natural
language [16]. Subsuquently this hypothesis has led to lots of research on
Artificial Intelligence (AI) for software engineering [32, 33]. With the
introduction of Generative Artificial Intelligence (GenAI) - a type of
artificial intelligence (AI), both the software development processes and
tooling have started to change fast. Further, GenAI can revolutionize software
development by automating repetitive tasks, improving code quality, enhancing
collaboration, providing data-driven insights, and ultimately accelerating the
development lifecycle [31, 25]. There is a growing research into how to use
Copilot [28], or Generative AI systems such as Chat GPT [37], and its
capability to automate software engineering tasks [20]. However, good tooling
is not enough.

In order for a company to succeed with software product development, well-
working teams and good processes are key. Software engineering is a social
activity that is focused on close cooperation and collaboration between all
team members [21] and across teams in the organization [2]. Therefore, it is
important to note that while AI has great potential, it also comes with
challenges [1] such as ethical considerations, data privacy concerns, the need
for skilled professionals to handle the technology within software teams, and
a potential change in the team dynamics. However, research on team dynamics is
lacking. In order to understand the effects on team-dynamics however we also
need to consider the individual work practices, to grasp the effects on a team
level. This paper explores how are software engineer work practices
transformed, and potential impact on the transformation on collaboration.

We have interviewed 13 data scientists, managers, developers, designers, and
frontend developers to investigate how they use GenAI technology and how their
workday has changed. Finally, we discuss how this technology might affect
software development teamwork.

##  2 Related work

###  2.1 Productivity and work satisfaction

Competing for talents requires a conscious effort to offer an attractive
workplace [24]. Further, the ability to balance the need and nature of the
workdays for different team members is directly related to the outcome of the
product [35]. For software developers, Meyer et al. [22] outline a framework
that describes what makes a good workday. There are three main factors: value
creation, efficient use of time, and perception. Value creation is about
whether or not the developers feel they are creating something, and the factor
has six sub-factors. The second factor, efficient use of time, has two sub-
factors, meeting expectations and the ability to work focused. In essence, the
assessment of a workday being good or bad is largely influenced by the
expectations for the day. For example, if one anticipates a day filled with
meetings, the day can be considered good even if most of the time is spent in
meetings. However, if one hopes for a day of focused work and the day is
filled with meetings, the day is perceived as a bad workday. Coworker
interruptions were specifically described as negatively influencing
developers’ ability to focus or work as planned, although being able to help a
co-worker was generally considered positive and rewarding. Lastly, perception
is about how they perceive their own productivity.

Developer satisfaction and work productivity are related, therefore they need
to be key considerations for software companies [15]. More productive
developers may be more satisfied, and more satisfied developers may be more
productive. Autonomy, being able to complete tasks, and technical skills all
affect productivity. By introducing new technology like GenAI, a team member’s
productivity may be positively affected. At the same time work culture and
team collaboration are important for job satisfaction. An increased reliance
on tools like GenAI may enhance individual productivity while inadvertently
reducing inter-team interactions, ultimately affecting long-term job
satisfaction and collective productivity. Introducing GenAI in software teams
is therefore a balancing act.

###  2.2 Software development, knowledge work and technology

Software engineering requires the input and consolidation of various
information to produce code [26]. Furthermore, with the advent of DevOps with
its increase in speed of delivering continuously [13], increased accessibility
to third-party libraries and frameworks, the process of software engineering
has shifted from being about understanding the computer and the programming
language towards understanding how to compose relevant libraries and
frameworks, with applicable testing.

Software development encompasses more than just programming and teamwork, it
also involves actively seeking knowledge online and in knowledge management
systems [12], conducting testing and code reviewing [14], and taking advantage
of software such as Integrated Development Environments. IDEs has been a
researched topic for quite some time [26] as well as how online resources [8,
18] aid and enhance the development process, both in speed and quality across
varying ranges of experience. Through the use of IDEs, software engineers have
gotten access to capabilities for refactoring, debugging, source repositories,
third-party plugins[26] and auto-completion of code [6]. In addition,
developers need to browse through a plethora of different files in existing
software solutions in order to get a grasp of how changes to the code need to
be implemented [17].

More recently, better auto-completion methodologies and technologies have been
introduced to provide more context-relevant suggestions using statistical
methods [6], and the naturalness of software [16] is a great target for
utilizing natural language processing and generative AI. Github Copilot has
shown promising effects for assisting developers in writing code, assisting
with test writing [25, 4]. Early studies on knowledge work show that
generative AI are able to disseminate knowledge previously shown as tacit[7]
and dramatically increase both quality and production[10]. Both studies show
that the effects are most noticeable for the lowers skilled workers while
higher skilled workers have a lower increase in prodcution and quality.

###  2.3 Teams, knowledge sharing and performance

Software product development is done in teams [19], therefore, the success of
software development depends significantly on team performance. Today the
premise is that software teams should be autonomous or self-managed [27]. In
their review, Dickinson and McIntyre [11] identified and defined seven core
components of teamwork. Using these components and their relationships as a
basis, they proposed the teamwork model that is used in this work. The model
consists of a learning loop of the following basic teamwork components:
communication, team orientation, team leadership, monitoring, feedback,
backup, and coordination. Later Moe et al. [23] used this model to explain
agile teamwork. The introduction of GenAI is likely to affect these teamwork
components.

##  3 Research Method and Analysis

This study was conducted in the context of two research programs on software
development processes, where several companies introduced Generative
Artificial Intelligence (GenAI) in their product development process. GenAI,
especially those built on LLMs, is a new phenomenon that has not been
previously studied. Due to the uncertain nature of the phenomenon, we chose an
exploratory multi-case study [38]. We selected our informants using snowball
sampling [3] in Slack asking for subjects that used GenAI for a wide range of
activities. As of the tools used, our studies found that ChatGPT and GitHub
Copilot were the most common for code and text, while some reported that they
used Midjourney and DALL-E 2 for image creation.

###  3.1 Data Collection and Analysis

We interviewed 13 people, as shown in Table 1. The informant group had a broad
range of roles: data scientists, managers, developers, designers, and front-
end developers. Based on a literature review, we developed a semi-structured
interview guide. Questions included: How do you use GenAI services? and Which
effects do you get from using them?. The interviews were done by the first,
third, fourth, and fifth authors to spread out any subjective biases.

The analysis was divided into two cycles of coding as suggested by Saldana
[29], with the third and first author conducting a combination of descriptive
and initial coding [9] on the first eight interviews. Then the third and first
authors had a discussion about the emerging categories and themes. This led to
a revised interview guide. Finally, the last five interviews were conducted.

After the last round of interviews, the fourth author performed a descriptive
coding of the remaining interviews. At the same time, the first author
performed a second cycle [29] focused coding of all interviews. Then, the
observed themes and categories were merged through mutual workshops and
discussions with all authors.

Table 1: Data sources ID |  Role | Work experience in years
---|---|---
I1 |  Developer & Team lead | 5
I2 |  Developer | 5
I3 |  Technical Strategy Consultant & Director | 30
I4 |  Tech Lead & Machine learning engineer | 6
I5 |  Principal Engineer and Enterprise Architect | 15
I6 |  Data Science Manager | 6
I7 |  Developer | 10
I8 |  CTO | 25
I9 |  Director | 30
I10 |  Developer | N/A
I11 |  Designer | 13
I12 |  Designer | 3
I13 |  Developer | 3

##  4 What is Generative AI Used for in Software Development?

Software development consists of a number of activities, ranging across
multiple roles in cross-functional teams. When using source repository systems
or IDEs, the use case is often clear. However, the use of GenAI takes on a
much more individual form. There are currently no standards or norms for how,
when, and for what purpose you should apply GenAI to, and employees in
software-intensive organizations are using it based on their own preferences.
GenAI tools for a wide range of activities. See Table 2 for an overview of
such activities.

The type of GenAI activities and utilization depends on individual
preferences, the task to be solved, and the user’s role in the organization.
Developers typically use GenAI when working with the source code, while
managers use it for, e.g. organizing workshops or creating content for
PowerPoint presentations.

###  4.1 Asking for assistance when stuck

When a person was stuck on a particular problem or did not know how to
proceed, ChatGPT was used as an assistant or fellow team member, where
interacting with it using chat could help a person solve complex problems or
get increased progress. For non-technical problems, this could be a case of
writer’s block, formulations, or when they are zoning out: _”For me, the main
thing is to get unstuck, whether I am struggling with writer’s block or
formulations, just by interacting with ChatGPT and getting an immediate
response is something else.”_

This highlights that there is an effect of just having the chat window open,
and getting feedback without interrupting others. Formulating the problem to
ChatGPT made it easier to keep focus on the task, helped on the thought
processes, and helped see the problem in a new light. Developers referred to
such interaction with ChatGPT as rubber-ducking. The idea of rubber-ducking is
to explain the problem one seeks to solve to an inanimate object (e.g. a
rubber duck), in an attempt to achieve a deeper understanding of the problem
and a potential solution through the process of explaining it to someone (or
something) using natural language.

Using GenAI as a sparring partner was both faster than asking human colleagues
and also took away the feeling of disturbing them in their work. Further,
being able to formulate the question as you would to a _human_ felt easier
than the alternate Google search, where you need to consider the specific
keywords, and what results they can give you.

Table 2: List of GenAI Activities Activity |  Description
---|---
Asking for assistance when stuck |  When stuck on a particular task, GenAI can help getting out of the slump.
Learning |  GenAI provide an interactive way of learning new things.
Creating a virtual environment for a product |  By asking GenAI to provide an simulated/virtual environment to learn and test products.
PowerPoint and email writing |  GenAI is useful for helping with writing text for email, powerpoint.
Non-technical boilerplate |  Providing a boilerplate for how to get started with powerpoint, workshops.
Boilerplate code |  GenAI can provide boilerplate code that acts as a skeleton for further development.
Working with existing code |  GenAI are used for refactoring, adding small features, making code more robust, converting code, debugging, writing tests, Search Engine Optimization (SEO).

###  4.2 Learning

GenAI provided more opportunities and avenues for engagement in learning
compared to reading books, using Google, or watching videos. One approach was
to engage interactively with the chat, assigning a role to the AI like ”act as
a tester”, and then engaging with that persona to learn about testing. They
could then ask that persona to explain a particular topic like they were doing
testing for the first time.

_”And then I continue. And I notice that I learn much faster this way. Because
it’s like having a personal tutor. Where you can ask yourself questions. And
then I always have to double-check.”_

The same approach was also applied when working on code, where using new
features, or when working on areas that the informants were not that
knowledgeable about, a data scientist explained how to use the technology to
learn more about programming: _”Almost as if I were asking someone much more
skilled, like a developer in this case.”_

###  4.3 Virtual environments

Creating a virtual environment for a product was used to develop software for
a trading platform. They engaged with the Chat GPT and asked it to simulate
that it was a stock exchange. They then provided the Chat GPT with information
about which stocks could be traded at the exchange and asked it to simulate
different trading scenarios. This provided a novel way for the informant to
understand the intricacies of a stock exchange. Further, this means that the
Chat GPT had the context for the particular trading platform the informants
were interested in.

_”And then I said, ”now I’m going to make an application out of this in such-
and-such language.” And so it has the context for everything while I kept
asking it further questions.”_ This integrated approach to both understanding
a domain, also then produced the relevant context that ChatGPT could use to
generate relevant code.

###  4.4 Copywriting

Maybe not surprisingly, Chat GPT was used to assist in copywriting text,
especially useful when integrated into the tool the informant was using,
getting live feedback; this was particularly useful for persons that were not
native or fluent in English or Norwegian. However, some experienced that GenAI
was not very useful for email and text writing for two main reasons, there was
a significant overhead in engaging sufficiently with ChatGPT to create emails,
and the quality did not get better.

_”I think I have asked it to write emails, but for me it is just faster to
write it myself. The formulation was better though.”_

###  4.5 Boilerplating code and text

Getting started with a relatively novel coding project in any company requires
quite a lot of boilerplate code; this type of code does not add functionality
relevant to the business case but is required to get the project up and
running with the necessary declarations and structures. Both back-end and
front-end developers used ChatGPT to create tailored boilerplate code:

_”If I have a task, to create a list of tricks with something, and thumbs up
and thumbs down on each element, for instance. I often start by describing
what I want to ChatGPT. Then, it writes the code for me.”_ GenAI was also used
for repetitive or tedious non-technical tasks. For example, managers and
architects stated to use ChatGPT to consolidate text used for production of
bid to customers. One manager explained, _”A bid I would normally have spent a
lot of time in writing, I only spent 20 minutes on. Previously I would have
spent a lot of time, looking for previous bids, adapting it and merging it. It
is terrible to say it out loud [laughing], as this kind of is in someway
reducing the need for my work. This type of work is what the company pays me
to do.”_

Another example is when you are building up technical specifications and
technical architectures where the style of the text is quite consistent but
the content varies between use cases. Or getting feedback on emails, and
getting a headstart on the writing of the text.

###  4.6 Working with existing code

This was the most common activity among software developers. GenAI was used on
many different tasks, ranging from refactoring or simplifying code, code
review, translating code from one programming language to another, and simply
explaining the code. Testing was also well-suited for GenAI utilization, given
its repetitive nature, GenAI was used to create numerous tests for the code.
The informants also noted that the generated tests sometimes accounted for
scenarios and test cases that they themselves had not thought of.

_”It was mostly a matter of thinking up all the things that could go wrong and
creating unit tests for them. And that’s where CoPilot was brilliant, as it
came up with things that could go wrong that I had never thought of.”_

##  5 How and why do we interact with GenAI?

In the previous section, we described how GenAI is used for a variety of
activities. In the studied companies GenAI was becoming an integrated part of
their daily work, and most explained that they used GenAI daily, or ”all the
time”.

Among the study participants we found two styles of interaction: _simple
dialogue_ and _advanced dialogue extended with prompt engineering_. The
interaction style depended on the work context and types of problems to be
solved. Table 3 contains an overview of the effects and drawbacks from
interacting with GenAI.

Table 3: Use of GenAI - Benefits and Challenges Mode |  Benefits |  Challenges
---|---|---
Simple |  • Asking questions is easier than searching • ChatGPT immediately provides an (almost) usable result • More efficient • More fun • More time to learn • Increased motivation and work satisfaction |  • Input cleaning • Lack of tool integration • Lack of information after 2021 • Output needs to be worked on • Culturally biased output
Advanced (Simple and Prompt engineering) |  • Interactive learning • More precise answers • Ability to take on different roles • Pair-prompt engineering • ChatGPT as advisor - rubberducking |  • Limited context ability • Less pair-programming • Still requires other people when the complexity increases • Prompt engineering requires competence

###  5.1 Effects

By spending less time on manual and repetitive tasks, the improved
productivity brought more enjoyment, motivation and fun to the work. The
repetitive tasks were seen as menial, and not particularly mentally
challenging. Further, as time was freed up, more time could be spent on
creative and challenging tasks. Moreover, engaging with the GenAI itself was
experienced as fun and increased the motivation to experiment with different
applications of the new technology.

Interacting through dialogue with ChatGPT increased engagement. It was
experienced as a more ”natural” engagement then searching for answers to
problems on Google. Having a dialogue with ChatGPT was also described as
faster than concocting the necessary string of Google search keywords.
Moreover, ChatGPT responds immediately with the, assumed, correct answer to
the question, while googling often required additional steps, vetting the
correct site on the search page, entering the particular page, and analysing
the web page for the potential answer to the question. One informant was so
conscious about speed that they deliberately chose GPT v3.5 over v4 in certain
cases (at the time of our data collection v3.5 was faster than v4) , where the
precision and quality of the v3.5 answer was assumed to be sufficient.

GenAI’s utility also extended beyond quick and precise answers, with
informants reporting a freedom in interacting with an artificial tool rather
than having to deal with the social considerations involved in asking a team
member.

_”Yeah, so you don’t need to be too polite either. You don’t have to have the
correct phrasing or anything. You can just throw something out, I feel. Then
you can get an answer, and if it’s not quite right, you can refine the
question again.”_

The threshold of asking ChatGPT was significantly lower than asking another
person or in a Slack channel. This threshold for asking colleagues could
potentially be high in a busy work environment, as one does not wish to
interrupt an already-busy colleague. Further, you get feedback immediately,
while it might take a while to get feedback on Slack.

###  5.2 Challenges

While there are many positive benefits of using GenAI, there are also
challenges. The elusiveness of data confidentiality, data policy, and
sensitivity meant that everyone was acutely conscious about which data to
input into the chat interface. This made the work process somewhat awkward,
requiring cleansing and anonymization of the text being sent into ChatGPT.
Developers in companies using open-source technology were less lenient in
protecting code than those in companies with internal code repositories.
Moreover, the general lack of tool integration meant that there was a
substantial amount of copy-paste to move text and code between different
windows. One developer using Copilot X reported that the integration in the
IDE meant that the code could be autocompleted, and explained by ChatGPT in a
seamless process, which reduced their work immensely: _”I think it would have
been easier to adopt a GenAI tool if I had used something like Copilot.
Because then it would have been, in a way, integrated into the workflow.”_

With regards to the output, all informants noted that the content produced by
GenAI, regardless of tool, seldom represented a final product and typically
required further refinement to be applicable in a real-world context. The
general attitude from the interviewees was that they expected the output to be
wrong.

Regarding technological development, which is characterized by a rapid pace
and a increasing number of available libraries and technology, the cut off
date for ChatGPT’s training data in September 2021 represented a significant
drawback, were the error-rate was annoyingly high.

One architect creating project startup documents, experienced that ChatGPT was
culturally biased towards how more hierarchical companies would perform
activities in a project. This meant that ChatGPT had to be prompted with
specific information regarding the methodology and project practices:

_”You kind of have to trick it into the right context if it’s (GenAI) going to
be part of agile processes.”_

###  5.3 Prompt engineering

Several interviewees talked about how the quality of their prompt affected the
quality of the response, and how the use of prompt engineering techniques like
contextualizing the problem, using personas, etc. to guide and steer the
dialogue with ChatGPT. Prompt engineering was applied to all the activities in
table 2. One informant explained asking ChatGPT to create a description of the
most critical code reviewer in the world. They then told ChatGPT to act like
this description while reviewing the codein a pull request. Another more
technical aspect was telling ChatGPT to act like an SQL database to test
queries. The effect of using prompt engineering was seen as a matter of
precision and quality, thus reducing the time spent on working on modifying
the output. One explained the usage of prompt engineering as follows:

_”It’s like putting up fences on the bowling lane and then narrowing it down
even more. It can almost only go one way, and that’s a strike.”_

An important prompt engineering technique was assigning different roles to
ChatGPT for the same question to get more than one perspective or answer on a
problem. One explained,

_”I want you to respond like a wealth manager,” ”I want you to respond like a
friend,” or ”like a so-and-so…” And then you get different answers.”_

Using prompt engineering while writing code was described as feeling similar
to programming with a partner. The flip side was that the developers mentioned
that they were doing less pair programming as they were getting the wanted
rubber ducking effect from using GenAI.

##  6 Discussion

One of the notable consequences of integrating GenAI tools into software
development tasks is a visible shift in collaborative communication dynamics.
Some of the informants appear to have a growing inclination to consult AI-
driven solutions for issues and tasks they previously discussed with their
human colleagues. This shift can have dramatic effects on the team’s ability
to perform. According to Liu et al., [19], a team’s ability to perform is
highly dependent on the knowledge sharing of the team. This implies that
reducing knowledge sharing by replacing this with Generative should be
observed. This opposes the findings by Brynjolfsson et al. [7], where
knowledge dissemination between high-skilled and low-skilled workers in
customer service. These findings point to a significant difference between
work done by teams in software development and individual work in customer
service. However, we find that individuals become more efficient and save
time, which they spend on more rewarding tasks.

If team members reduce their interactions in favor of focusing on individual
tasks, a phenomenon known as an isomorphic team structure may emerge. The
advantages of this structure are that it is organizationally simple, allows
many tasks to be completed in parallel, and can clearly define and understand
task responsibilities. However, the effect of such a structure is that the
developers focused on their own modules and often created their own plans and
made their own decisions. In addition, problems are seen as personal,
individual goals are more important than team goals, and team members become
less aware of what others are doing and get less support and help from others
[23]. In a good working team, learning is a continuous feedback, see Figure
1(a). By introducing GenAI; this loop will be disrupted, or reduced, Figure
1(b), thus reducing teamwork performance[23]. Additionally, this can also
contribute to making persons less satisfied as helping others is a key factor
for good workdays [22].

(a) Regular learning loop

(b) Disrupted learning loop

Figure 1: Regular and disrupted learning loops.

This model posits that the incorporation of GenAI in software development may
disrupt the established learning loop. Such disruption will subsequently
affect individual and team performance in software development. While it is
anticipated that GenAI might enhance individual performance by streamlining
tasks, there is a concurrent risk of diminishing overall team performance.

However, everything is not dark; as multiple informants noted, they had an
increasing amount of knowledge sharing on how to use GenAI in their work and
context. Notably, the practice of ”pair prompt engineering” has emerged, akin
to the concept of pair programming. This approach facilitates knowledge
sharing [34] both on-site and when working remotely. This can thus involve a
shift in how the programmers program, creating yet another abstraction layer
for code production.

##  7 Concluding remarks

In essence, GenAI serves a dual purpose: making everyday tasks more efficient
and reigniting creative thinking for leaders and developers. By automating the
production of routine code snippets and related tasks, these tools enable
programmers to focus on higher-level conceptualization and innovation,
resulting in enhanced productivity and code quality. This is similar to
findings by Meyer et al. [22], where good workdays are understood as days
where they feel productive and are able to work focused. In addition, similar
to Brynjolfsson et al. where there is knowledge dissemination through the
GenAI [7], we observe that there are data scientists using GenAI for coding
purposes and frontend developers getting assistance in back-end development.
Both programmers and leaders acknowledged the potential of generative AI in
freeing up valuable time and cognitive resources that could be better
allocated to more creative and complex problem-solving tasks.

This is reported to enhance both efficiency and enjoyment. By automating the
production of routine code snippets and documentation, these GenAI enabled
programmers to focus on higher-level conceptualization and other more
complicated tasks, resulting in higher reported productivity. Most informants
reported that AI reduced the amount of time developers spent on projects.

## Acknowledgments

This work was supported by the Research Council of Norway grants, 321477, and
309344, and the companies Knowit, and Iterate through the research projects
Transformit and 10XTeams.

## References

  * [1] Bender, E.M., Gebru, T., McMillan-Major, A., Shmitchell, S.: On the dangers of stochastic parrots: Can language models be too big? In: Proceedings of the 2021 ACM conference on fairness, accountability, and transparency. pp. 610–623 (2021)
  * [2] Berntzen, M., Stray, V., Moe, N.B., Hoda, R.: Responding to change over time: A longitudinal case study on changes in coordination mechanisms in large-scale agile. Empirical Software Engineering 28(5), 114 (2023). https://doi.org/10.1007/s10664-023-10349-0
  * [3] Biernacki, P., Waldorf, D.: Snowball sampling: Problems and techniques of chain referral sampling. Sociological methods & research 10(2), 141–163 (1981), publisher: Sage Publications Sage CA: Los Angeles, CA
  * [4] Bird, C., Ford, D., Zimmermann, T., Forsgren, N., Kalliamvakou, E., Lowdermilk, T., Gazit, I.: Taking Flight with Copilot: Early insights and opportunities of AI-powered pair-programming tools. Queue 20(6), 35–57 (Dec 2022). https://doi.org/10.1145/3582083, https://dl.acm.org/doi/10.1145/3582083
  * [5] Bosch, J., Olsson, H.H.: Digital for real: A multicase study on the digital transformation of companies in the embedded systems domain. Journal of Software: Evolution and Process 33(5) (2021). https://doi.org/10.1002/smr.2333
  * [6] Bruch, M., Monperrus, M., Mezini, M.: Learning from examples to improve code completion systems. In: Proceedings of the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering. pp. 213–222 (2009)
  * [7] Brynjolfsson, E., Li, D., Raymond, L.R.: Generative AI at work. Tech. rep., National Bureau of Economic Research (2023)
  * [8] Chatterjee, P., Kong, M., Pollock, L.: Finding help with programming errors: An exploratory study of novice software engineers’ focus in stack overflow posts. Journal of Systems and Software 159, 110454 (2020), publisher: Elsevier
  * [9] Corbin, J., Strauss, A.: Basics of qualitative research: Techniques and procedures for developing grounded theory. Sage publications (2014)
  * [10] Dell’Acqua, F., McFowland, E., Mollick, E.R., Lifshitz-Assaf, H., Kellogg, K., Rajendran, S., Krayer, L., Candelon, F., Lakhani, K.R.: Navigating the Jagged Technological Frontier: Field Experimental Evidence of the Effects of AI on Knowledge Worker Productivity and Quality (Sep 2023). https://doi.org/10.2139/ssrn.4573321, https://papers.ssrn.com/abstract=4573321
  * [11] Dickinson, T.L., McIntyre, R.M.: A conceptual framework for teamwork measurement. In: Team performance assessment and measurement, pp. 31–56. Psychology Press (1997)
  * [12] Dingsøyr, T., Bjørnson, F.O., Shull, F.: What Do We Know about Knowledge Management? Practical Implications for Software Engineering. IEEE Software 26(3), 100–103 (May 2009). https://doi.org/10.1109/MS.2009.82, conference Name: IEEE Software
  * [13] Fitzgerald, B., Stol, K.J.: Continuous software engineering: A roadmap and agenda. Journal of Systems and Software (2015). https://doi.org/http://dx.doi.org/10.1016/j.jss.2015.06.063
  * [14] Florea, R., Stray, V.: A global view on the hard skills and testing tools in software testing. In: 2019 ACM/IEEE 14th International Conference on Global Software Engineering (ICGSE). pp. 143–151. IEEE (2019). https://doi.org/10.1109/ICGSE.2019.00035
  * [15] Forsgren, N., Storey, M.A., Maddila, C., Zimmermann, T., Houck, B., Butler, J.: The SPACE of Developer Productivity: There’s more to it than you think. Queue 19(1), 20–48 (2021)
  * [16] Hindle, A., Barr, E.T., Gabel, M., Su, Z., Devanbu, P.: On the naturalness of software. Communications of the ACM 59(5), 122–131 (2016), publisher: ACM New York, NY, USA
  * [17] Kersten, M., Murphy, G.C.: Using task context to improve programmer productivity. In: Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering. pp. 1–11 (2006)
  * [18] Li, A., Endres, M., Weimer, W.: Debugging with stack overflow: web search behavior in novice and expert programmers. In: Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Software Engineering Education and Training. pp. 69–81. ICSE-SEET ’22, Association for Computing Machinery, New York, NY, USA (Oct 2022). https://doi.org/10.1145/3510456.3514147, https://dl.acm.org/doi/10.1145/3510456.3514147
  * [19] Liu, M.L., Hsieh, M.W., Hsiao, C., Lin, C.P., Yang, C.: Modeling knowledge sharing and team performance in technology industry: the main and moderating effects of happiness. Review of Managerial Science 14(3), 587–610 (Jun 2020). https://doi.org/10.1007/s11846-018-0301-4, https://doi.org/10.1007/s11846-018-0301-4
  * [20] Melegati, J., Guerra, E.: Dante: a taxonomy for the automation degree of software engineering tasks. arXiv (2023)
  * [21] Mens, T., Cataldo, M., Damian, D.: The Social Developer: The Future of Software Development [Guest Editors’ Introduction]. IEEE Software 36(1), 11–14 (2019), publisher: IEEE
  * [22] Meyer, A.N., Barr, E.T., Bird, C., Zimmermann, T.: Today was a good day: The daily life of software developers. IEEE Transactions on Software Engineering 47(5), 863–880 (2019), publisher: IEEE
  * [23] Moe, N.B., Dingsøyr, T., Dybå, T.: A teamwork model for understanding an agile team: A case study of a Scrum project. Information and Software Technology 52(5), 480–491 (2010), publisher: Elsevier
  * [24] Moe, N.B., Stray, V., Smite, D., Mikalsen, M.: Attractive Workplaces: What are Engineers Looking For? IEEE Software (2023), publisher: IEEE
  * [25] Muller, M., Ross, S., Houde, S., Agarwal, M., Martinez, F., Richards, J., Talamadupula, K., Weisz, J.D.: Drinking Chai with Your (AI) Programming Partner: A Design Fiction about Generative AI for Software Engineering. In: HAI-GEN Workshop at IUI 2022: 3rd Workshop on Human-AI Co-Creation with Generative Models (2022), https://hai-gen.github.io/2022/papers/paper-HAIGEN-MullerMichael.pdf
  * [26] Murphy, G., Kersten, M., Findlater, L.: How are Java software developers using the Eclipse IDE? IEEE Software 23(4), 76–83 (Jul 2006). https://doi.org/10.1109/MS.2006.105, conference Name: IEEE Software
  * [27] Ravn, J.E., Moe, N.B., Stray, V., Seim, E.A.: Team autonomy and digital transformation: Disruptions and adjustments in a well-established organizational principle. AI & SOCIETY 37(2), 701–710 (2022)
  * [28] Ross, S.I., Martinez, F., Houde, S., Muller, M., Weisz, J.D.: The programmer’s assistant: Conversational interaction with a large language model for software development. Proceedings of the 28th International Conference on Intelligent User Interfaces p. 491–514 (2023). https://doi.org/10.1145/3581641.3584037
  * [29] Saldaña, J.: The coding manual for qualitative researchers. SAGE, Los Angeles, 2nd ed edn. (2013), oCLC: ocn796279115
  * [30] Stray, V., Gundelsby, J.H., Ulfsnes, R., Brede Moe, N.: How agile teams make Objectives and Key Results (OKRs) work. In: Proceedings of the International Conference on Software and System Processes and International Conference on Global Software Engineering. pp. 104–109 (2022)
  * [31] Sun, J., Liao, Q.V., Muller, M., Agarwal, M., Houde, S., Talamadupula, K., Weisz, J.D.: Investigating explainability of generative AI for code through scenario-based design. In: 27th International Conference on Intelligent User Interfaces. pp. 212–228 (2022)
  * [32] Svyatkovskiy, A., Zhao, Y., Fu, S., Sundaresan, N.: Pythia: Ai-assisted code completion system. In: Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. pp. 2727–2735 (2019)
  * [33] Talamadupula, K.: Applied AI matters: AI4Code: applying artificial intelligence to source code. AI Matters 7(1), 18–20 (Mar 2021). https://doi.org/10.1145/3465074.3465080, https://dl.acm.org/doi/10.1145/3465074.3465080
  * [34] Tkalich, A., Moe, N.B., Andersen, N.H., Stray, V., Barbala, A.M.: Pair Programming Practiced in Hybrid Work. In: Proceedings of the 17th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM). Association for Computing Machinery, New York, NY, United States (2023)
  * [35] Tkalich, A., Ulfsnes, R., Moe, N.B.: Toward an agile product management: What do product managers do in agile companies? In: International Conference on Agile Software Development. pp. 168–184. Springer (2022)
  * [36] Ulfsnes, R., Mikalsen, M., Sporsem, T., Hatling, M.: Technology for knowledge work: A relational perspective. ECIS 2023 Research-in-Progress Papers (May 2023), https://aisel.aisnet.org/ecis2023_rip/48
  * [37] White, J., Hays, S., Fu, Q., Spencer-Smith, J., Schmidt, D.C.: Chatgpt prompt patterns for improving code quality, refactoring, requirements elicitation, and software design. arXiv (2023). https://doi.org/10.48550/arxiv.2303.07839
  * [38] Yin, R.K.: Case study research and applications: Design and methods. Los Angeles, UK: Sage (2018)


$Id:espcrc1.tex,v1.22004/02/2411:22:11speppingExp$ Interval cyclic edge-
colorings of graphsP.A. Petrosyan, S.T. Mkhitaryan

# Interval cyclic edge-colorings of graphs

P.A. Petrosyan, S.T. Mkhitaryan[MCSD] email<EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Informatics and Applied Mathematics,
Yerevan State University, 0025, Armenia  Institute for Informatics and
Automation Problems,
National Academy of Sciences, 0014, Armenia

###### Abstract

A proper edge-coloring of a graph $G$ with colors $1,\ldots,t$ is called an
_interval cyclic $t$-coloring_ if all colors are used, and the edges incident
to each vertex $v\in V(G)$ are colored by $d_{G}(v)$ consecutive colors modulo
$t$, where $d_{G}(v)$ is the degree of a vertex $v$ in $G$. A graph $G$ is
_interval cyclically colorable_ if it has an interval cyclic $t$-coloring for
some positive integer $t$. The set of all interval cyclically colorable graphs
is denoted by $\mathfrak{N}_{c}$. For a graph $G\in\mathfrak{N}_{c}$, the
least and the greatest values of $t$ for which it has an interval cyclic
$t$-coloring are denoted by $w_{c}(G)$ and $W_{c}(G)$, respectively. In this
paper we investigate some properties of interval cyclic colorings. In
particular, we prove that if $G$ is a triangle-free graph with at least two
vertices and $G\in\mathfrak{N}_{c}$, then $W_{c}(G)\leq|V(G)|+\Delta(G)-2$. We
also obtain bounds on $w_{c}(G)$ and $W_{c}(G)$ for various classes of graphs.
Finally, we give some methods for constructing of interval cyclically non-
colorable graphs.

Keywords: edge-coloring, interval coloring, interval cyclic coloring,
bipartite graph, complete graph.

##  1 Introduction

All graphs considered in this paper are finite, undirected, and have no loops
or multiple edges. Let $V(G)$ and $E(G)$ denote the sets of vertices and edges
of $G$, respectively. For a graph $G$, the number of connected components of
$G$ is denoted by $c(G)$. A graph $G$ is Eulerian if it has a closed trail
containing every edge of $G$. The degree of a vertex $v\in V(G)$ is denoted by
$d_{G}(v)$ (or $d(v)$), the maximum degree of $G$ by $\Delta(G)$, the diameter
of $G$ by $\mathrm{diam}(G)$, and the chromatic index of $G$ by
$\chi^{\prime}(G)$. The terms and concepts that we do not define can be found
in [3, 33].

A proper edge-coloring of a graph $G$ with colors $1,\ldots,t$ is an _interval
$t$-coloring_ if all colors are used, and the colors of edges incident to each
vertex of $G$ are form an interval of integers. A graph $G$ is _interval
colorable_ if it has an interval $t$-coloring for some positive integer $t$.
The concept of interval edge-coloring of graphs was introduced by Asratian and
Kamalian [1]. In [1, 2], the authors showed that if $G$ is interval colorable,
then $\chi^{\prime}(G)=\Delta(G)$. In [1, 2], they also proved that if a
triangle-free graph $G$ has an interval $t$-coloring, then
$t\leq\left|V(G)\right|-1$. Later, Kamalian [13] showed that if $G$ admits an
interval $t$-coloring, then $t\leq 2\left|V(G)\right|-3$. This upper bound was
improved to $2\left|V(G)\right|-4$ for graphs $G$ with at least three vertices
[8]. For an $r$-regular graph $G$, Kamalian and Petrosyan [18] showed that if
$G$ with at least $2r+2$ vertices admits an interval $t$-coloring, then $t\leq
2\left|V(G)\right|-5$. For a planar graph $G$, Axenovich [4] showed that if
$G$ has an interval $t$-coloring, then $t\leq\frac{11}{6}\left|V(G)\right|$.
In [12, 13, 24, 26], interval colorings of complete graphs, complete bipartite
graphs, trees, and $n$-dimensional cubes were investigated. The
$NP$-completeness of the problem of the existence of an interval coloring of
an arbitrary bipartite graph was shown in [29]. In [5, 6, 21, 25, 26, 27],
interval colorings of various products of graphs were investigated. In [2, 3,
6, 7, 9, 10, 11, 16, 17, 19], the problem of the existence and construction of
interval colorings was considered, and some bounds for the number of colors in
such colorings of graphs were given.

A proper edge-coloring of a graph $G$ with colors $1,\ldots,t$ is called an
_interval cyclic $t$-coloring_ if all colors are used, and the edges incident
to each vertex $v\in V(G)$ are colored by $d_{G}(v)$ consecutive colors modulo
$t$. A graph $G$ is _interval cyclically colorable_ if it has an interval
cyclic $t$-coloring for some positive integer $t$. This type of edge-coloring
under the name of “$\pi$-coloring”was first considered by Kotzig in [20],
where he proved that every cubic graph has a $\pi$-coloring with 5 colors.
However, the concept of interval cyclic edge-coloring of graphs was explicitly
introduced by de Werra and Solot [32]. In [32], they proved that if $G$ is an
outerplanar bipartite graph, then $G$ has an interval cyclic $t$-coloring for
any $t\geq\Delta(G)$. In [22], Kubale and Nadolski showed that the problem of
determining whether a given bipartite graph is interval cyclically colorable
is $NP$-complete. Later, Nadolski [23] showed that if $G$ is interval
colorable, then $G$ has an interval cyclic $\Delta(G)$-coloring. He also
proved that if $G$ is a connected graph with $\Delta(G)=3$, then $G$ has an
interval cyclic coloring with at most 4 colors. In [14, 15], Kamalian
investigated interval cyclic colorings of simple cycles and trees. For simple
cycles and trees, he determined all possible values of $t$ for which these
graphs have an interval cyclic $t$-coloring.

In this paper we investigate some properties of interval cyclic colorings. In
particular, we prove that if a triangle-free graph $G$ with at least two
vertices has an interval cyclic $t$-coloring, then $t\leq|V(G)|+\Delta(G)-2$.
For various classes of graphs, we also obtain bounds on the least and the
greatest values of $t$ for which these graphs have an interval cyclic
$t$-coloring. Finally, we describe some methods for constructing of interval
cyclically non-colorable graphs.

##  2 Notations, definitions and auxiliary results

We use standard notations $C_{n},K_{n}$ and $Q_{n}$ for the simple cycle,
complete graph on $n$ vertices and the hypercube, respectively. We also use
standard notations $K_{m,n}$ and $K_{l,m,n}$ for the complete bipartite and
tripartite graph, respectively, one part of which has $m$ vertices, other part
has $n$ vertices and a third part has $l$ vertices.

A _partial edge-coloring_ of $G$ is a coloring of some of the edges of $G$
such that no two adjacent edges receive the same color. If $\alpha$ is a
partial edge-coloring of $G$ and $v\in V(G)$, then $S\left(v,\alpha\right)$
denotes the set of colors appearing on colored edges incident to $v$.

A graph $G$ is _interval colorable_ if it has an interval $t$-coloring for
some positive integer $t$. The set of all interval colorable graphs is denoted
by $\mathfrak{N}$. For a graph $G\in\mathfrak{N}$, the least and the greatest
values of $t$ for which it has an interval $t$-coloring are denoted by $w(G)$
and $W(G)$, respectively.

A graph $G$ is _interval cyclically colorable_ if it has an interval cyclic
$t$-coloring for some positive integer $t$. The set of all interval cyclically
colorable graphs is denoted by $\mathfrak{N}_{c}$. For a graph
$G\in\mathfrak{N}_{c}$, the least and the greatest values of $t$ for which it
has an interval cyclic $t$-coloring are denoted by $w_{c}(G)$ and $W_{c}(G)$,
respectively. The _feasible set_ $F(G)$ of a graph $G$ is the set of all $t$’s
such that there exists an interval cyclic $t$-coloring of $G$. The feasible
set of $G$ is _gap-free_ if $F(G)=\left[w_{c}(G),W_{c}(G)\right]$. Clearly, if
$G\in\mathfrak{N}$, then $G\in\mathfrak{N}_{c}$ and $\chi^{\prime}(G)\leq
w_{c}(G)\leq w(G)\leq W(G)\leq W_{c}(G)\leq|E(G)|$.

Let $\left\lfloor a\right\rfloor$ denote the largest integer less than or
equal to $a$. For two positive integers $a$ and $b$ with $a\leq b$, we denote
by $\left[a,b\right]$ the interval of integers $\left\\{a,\ldots,b\right\\}$.
By $\left[a,b\right]_{even}$ ($\left[a,b\right]_{odd}$), we denote the set of
all even (odd) numbers from the interval $\left[a,b\right]$.

In [1, 2], Asratian and Kamalian obtained the following two results.

###### Theorem 1

If $G\in\mathfrak{N}$, then $\chi^{\prime}(G)=\Delta(G)$. Moreover, if $G$ is
a regular graph, then $G\in\mathfrak{N}$ if and only if
$\chi^{\prime}(G)=\Delta(G)$.

###### Theorem 2

If $G$ is a connected triangle-free graph and $G\in\mathfrak{N}$, then

$W(G)\leq|V(G)|-1$.

For general graphs, Kamalian proved the following

###### Theorem 3

([13]). If $G$ is a connected graph with at least two vertices and
$G\in\mathfrak{N}$, then

$W(G)\leq 2|V(G)|-3$.

Note that the upper bound in Theorem 3 is sharp for $K_{2}$, but if $G\neq
K_{2}$, then this upper bound can be improved.

###### Theorem 4

([8]). If $G$ is a connected graph with with at least three vertices and
$G\in\mathfrak{N}$, then

$W(G)\leq 2|V(G)|-4$.

In [30], Vizing proved the following well-known result.

###### Theorem 5

For every graph $G$,

$\Delta(G)\leq\chi^{\prime}(G)\leq\Delta(G)+1$.

###### Corollary 6

If $G$ is a regular graph, then $G\in\mathfrak{N}_{c}$ and
$w_{c}(G)=\chi^{\prime}(G)$.

From Theorems 1 and 5, we get

###### Corollary 7

$\mathfrak{N}\subset\mathfrak{N}_{c}$.

Although all regular graphs are interval cyclically colorable, there are many
graphs that have no interval cyclic coloring. In Fig. 1, we present the
smallest known interval cyclically non-colorable graph.

Figure 1: The interval cyclically non-colorable graph.

We also need the generalizations of Theorems 2,3 and 4 for disconnected
graphs. It can be easily proved by induction on the number of connected
components that the following two lemmas hold.

###### Lemma 8

If $G$ is a triangle-free graph and $G\in\mathfrak{N}_{c}$, then

$W(G)\leq|V(G)|-c(G)$.

###### Lemma 9

If $G$ is a graph with at least two vertices and $G\in\mathfrak{N}_{c}$, then

$W(G)\leq 2|V(G)|-3\cdot c(G)$.

Moreover, if $G$ has at least three vertices, then

$W(G)\leq 2|V(G)|-4\cdot c(G)$.

##  3 Some general results

In this section we derive some upper bounds for $W_{c}(G)$ depending on the
number of vertices, degrees and diameter for connected graphs, triangle-free
graphs, and, in particular, for bipartite graphs. Next we show that there are
graphs $G$ for which $w_{c}(G)>\chi^{\prime}(G)$. We also investigate the
feasible sets of interval cyclically colorable graphs. In particular, we show
that if $G$ is interval colorable, then $\left[\Delta(G),W(G)\right]\subseteq
F(G)$. On the other hand, we also show that there are interval cyclically
colorable graphs for which feasible sets are not gap-free.

Our first two theorems give upper bounds for $W_{c}(G)$ depending on the
number of vertices and the maximum degree of the interval cyclically colorable
graph $G$.

###### Theorem 10

If $G$ is a connected triangle-free graph with at least two vertices and
$G\in\mathfrak{N}_{c}$, then $W_{c}(G)\leq|V(G)|+\Delta(G)-2$.

  * Proof.

Consider an interval cyclic $W_{c}(G)$-coloring $\alpha$ of $G$. If for each
$u\in V(G)$, $S(u,\alpha)$ is an interval of integers, then $G\in\mathfrak{N}$
and $W_{c}(G)\leq W(G)\leq|V(G)|-1\leq|V(G)|+\Delta(G)-2$, by Theorem 2 and
taking into account that $G$ is a connected triangle-free graph with at least
two vertices.

Now suppose that there exists $v_{0}\in V(G)$ such that $S(v_{0},\alpha)$ is
not an interval of integers. Since $\alpha$ is an interval cyclic
$W_{c}(G)$-coloring of $G$, for each $v\in V(G)$ such that $S(v,\alpha)$ is
not an interval, there are colors $k_{v}$ and $l_{v}$ such that

$S(v,\alpha)=\\{1,\ldots,k_{v}\\}\cup\\{W_{c}(G)-l_{v}+1,\ldots,W_{c}(G)\\}$.

Let $l^{\star}=\max_{\begin{subarray}{1}v\in V(G),\\\
S(v,\alpha)~{}is~{}not~{}an~{}interval\end{subarray}}l_{v}$. Clearly, $1\leq
l^{\star}\leq\Delta(G)-1$. Define an auxiliary graph $H$ as follows:

$V(H)=V(G)$ and

$E(H)=E(G)\setminus\\{e\colon\,e\in
E(G)\wedge\alpha(e)\in\\{W_{c}(G)-l^{\star}+1,\ldots,W_{c}(G)\\}\\}$.

Clearly, $H$ is a spanning subgraph of $G$. Now let us consider the
restriction of the coloring $\alpha$ on the edges of subgraph $H$ of $G$. Let
$\alpha_{H}$ be this edge-coloring. It is easy to see that $\alpha_{H}$ is an
interval $(W_{c}(G)-l^{\star})$-coloring of $H$. Moreover, since $H$ is a
triangle-free graph and $H\in\mathfrak{N}$, by Lemma 8, we have

$W_{c}(G)-l^{\star}\leq W(H)\leq|V(H)|-c(H)\leq|V(H)|-1=|V(G)|-1$.

This implies that $W_{c}(G)\leq|V(G)|+l^{\star}-1$. From this and taking into
account that $l^{\star}\leq\Delta(G)-1$, we obtain
$W_{c}(G)\leq|V(G)|+\Delta(G)-2$. $\square$

###### Corollary 11

If $G$ is a connected triangle-free graph with at least two vertices and
$G\in\mathfrak{N}_{c}$, then $W_{c}(G)\leq 2|V(G)|-3$. Moreover, if $G$ has at
least three vertices, then $W_{c}(G)\leq 2|V(G)|-4$.

Note that the upper bound in Theorem 10 is sharp for simple cycles, since
$W_{c}(C_{n})=n$.

###### Theorem 12

If $G$ is a connected graph with at least two vertices and
$G\in\mathfrak{N}_{c}$, then $W_{c}(G)\leq 2|V(G)|+\Delta(G)-4$. Moreover, if
$G$ has at least three vertices, then $W_{c}(G)\leq 2|V(G)|+\Delta(G)-5$.

  * Proof.

Consider an interval cyclic $W_{c}(G)$-coloring $\alpha$ of $G$. If for each
$u\in V(G)$, $S(u,\alpha)$ is an interval of integers, then $G\in\mathfrak{N}$
and $W_{c}(G)\leq W(G)\leq 2|V(G)|-3\leq 2|V(G)|+\Delta(G)-4$, by Theorem 3
and taking into account that $G$ is a connected graph with at least two
vertices. Moreover, if $G$ has at least three vertices, then $W_{c}(G)\leq
W(G)\leq 2|V(G)|-4\leq 2|V(G)|+\Delta(G)-5$, by Theorem 4.

Now suppose that there exists $v_{0}\in V(G)$ such that $S(v_{0},\alpha)$ is
not an interval of integers. Since $\alpha$ is an interval cyclic
$W_{c}(G)$-coloring of $G$, for each $v\in V(G)$ such that $S(v,\alpha)$ is
not an interval, there are colors $k_{v}$ and $l_{v}$ such that

$S(v,\alpha)=\\{1,\ldots,k_{v}\\}\cup\\{W_{c}(G)-l_{v}+1,\ldots,W_{c}(G)\\}$.

Let $l^{\star}=\max_{\begin{subarray}{1}v\in V(G),\\\
S(v,\alpha)~{}is~{}not~{}an~{}interval\end{subarray}}l_{v}$. Clearly, $1\leq
l^{\star}\leq\Delta(G)-1$. Define an auxiliary graph $H$ as follows:

$V(H)=V(G)$ and

$E(H)=E(G)\setminus\\{e\colon\,e\in
E(G)\wedge\alpha(e)\in\\{W_{c}(G)-l^{\star}+1,\ldots,W_{c}(G)\\}\\}$.

Clearly, $H$ is a spanning subgraph of $G$. Now let us consider the
restriction of the coloring $\alpha$ on the edges of the subgraph $H$ of $G$.
Let $\alpha_{H}$ be this edge-coloring. It is easy to see that $\alpha_{H}$ is
an interval $(W_{c}(G)-l^{\star})$-coloring of $H$. Since $H\in\mathfrak{N}$,
by Lemma 9, we have

$W_{c}(G)-l^{\star}\leq W(H)\leq 2|V(H)|-3\cdot c(H)\leq 2|V(H)|-3=2|V(G)|-3$.

Moreover, if $G$ has at least three vertices, then

$W_{c}(G)-l^{\star}\leq W(H)\leq 2|V(H)|-4\cdot c(H)\leq 2|V(H)|-4=2|V(G)|-4$.

This implies that $W_{c}(G)\leq 2|V(G)|+l^{\star}-3$. From this and taking
into account that $l^{\star}\leq\Delta(G)-1$, we obtain $W_{c}(G)\leq
2|V(G)|+\Delta(G)-4$. Moreover, if $G$ has at least three vertices, then
$W_{c}(G)\leq 2|V(G)|+\Delta(G)-5$. $\square$

###### Corollary 13

If $G$ is a connected graph with at least two vertices and
$G\in\mathfrak{N}_{c}$, then $W_{c}(G)\leq 3|V(G)|-5$. Moreover, if $G$ has at
least three vertices, then $W_{c}(G)\leq 3|V(G)|-6$.

Note that the first upper bound in Theorem 12 is sharp for $K_{2}$ and the
second upper bound is sharp for $K_{3}$, but we strongly believe that these
upper bounds can be improved. Next we give some upper bounds for $W_{c}(G)$
depending on degrees and diameter of the interval cyclically colorable
connected graph $G$.

###### Theorem 14

If $G$ is a connected graph and $G\in\mathfrak{N}_{c}$, then

$W_{c}(G)\leq 1+2\cdot{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)$,

where $\mathbf{P}$ is the set of all shortest paths in the graph $G$.

  * Proof.

Consider an interval cyclic $W_{c}(G)$-coloring $\alpha$ of $G$. Let us show
that $W_{c}(G)\leq 1+2\cdot{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)$. Suppose, to the contrary, that
$W_{c}(G)>1+2\cdot{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)$. In the coloring $\alpha$ of $G$, we consider
the edges with colors $1$ and
$2+{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)$. Let $e=u_{1}u_{2},e^{\prime}=w_{1}w_{2}$ and
$\alpha(e)=1,\alpha(e^{\prime})=2+{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)$. Without loss of generality we may assume that
a shortest path $P$ joining $e$ with $e^{\prime}$ joins $u_{1}$ with $w_{1}$,
where

$P=\left(v_{0},e_{1},v_{1},\ldots,v_{i-1},e_{i},v_{i},\ldots,v_{k-1},e_{k},v_{k}\right)$
and $v_{0}=u_{1}$, $v_{k}=w_{1}$.

Since $\alpha$ is an interval cyclic coloring of $G$, we have

either $\alpha(e_{1})\leq d_{G}(v_{0})$ or $\alpha(e_{1})\geq
W_{c}(G)-d_{G}(v_{0})+2$,

either $\alpha(e_{2})\leq\alpha(e_{1})+d_{G}(v_{1})-1$ or
$\alpha(e_{2})\geq\alpha(e_{1})-d_{G}(v_{1})+1$,

$\cdots\cdots\cdots\cdots\cdots\cdots$

either $\alpha(e_{i})\leq\alpha(e_{i-1})+d_{G}(v_{i-1})-1$ or
$\alpha(e_{i})\geq\alpha(e_{i-1})-d_{G}(v_{i-1})+1$,

$\cdots\cdots\cdots\cdots\cdots\cdots$

either $\alpha(e_{k})\leq\alpha(e_{k-1})+d_{G}(v_{k-1})-1$ or
$\alpha(e_{k})\geq\alpha(e_{k-1})-d_{G}(v_{k-1})+1$.

Summing up these inequalities, we obtain

either $\alpha(e_{k})\leq
1+{\sum\limits_{j=0}^{k-1}\left(d_{G}(v_{j})-1\right)}$ or $\alpha(e_{k})\geq
W_{c}(G)+1-{\sum\limits_{j=0}^{k-1}\left(d_{G}(v_{j})-1\right)}$.

Hence, we have either

$\alpha(e^{\prime})\leq\alpha(e_{k})+d_{G}(v_{k})-1\leq
1+{\sum\limits_{j=0}^{k}\left(d_{G}(v_{j})-1\right)}$ (1)

or

$\alpha(e^{\prime})\geq\alpha(e_{k})-d_{G}(v_{k})+1\geq
W_{c}(G)+1-{\sum\limits_{j=0}^{k}\left(d_{G}(v_{j})-1\right)}.$ (2)

On the other hand, by (1), we obtain

$2+{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)=\alpha(e^{\prime})\leq
1+{\sum\limits_{j=0}^{k}\left(d_{G}(v_{j})-1\right)}\leq
1+{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)$, which is a contradiction.

Similarly, by (2), we obtain

$2+{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)=\alpha(e^{\prime})\geq
W_{c}(G)+1-{\sum\limits_{j=0}^{k}\left(d_{G}(v_{j})-1\right)}\geq
W_{c}(G)+1-{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)$ and thus $W_{c}(G)\leq
1+2\cdot{\max\limits_{P\in\mathbf{P}}}{\sum\limits_{v\in
V(P)}}\left(d_{G}(v)-1\right)$, which is a contradiction. $\square$

###### Corollary 15

([23]). If $G$ is a connected graph and $G\in\mathfrak{N}_{c}$, then

$W_{c}(G)\leq 1+2(\mathrm{diam}(G)+1)\left(\Delta(G)-1\right)$.

###### Theorem 16

If $G$ is a connected bipartite graph and $G\in\mathfrak{N}_{c}$, then

$W_{c}(G)\leq 1+2\cdot\mathrm{diam}(G)\left(\Delta(G)-1\right)$.

  * Proof.

Consider an interval cyclic $W_{c}(G)$-coloring $\alpha$ of $G$. Let us show
that $W_{c}(G)\leq 1+2\cdot\mathrm{diam}(G)\left(\Delta(G)-1\right)$. Suppose,
to the contrary, that
$W_{c}(G)>1+2\cdot\mathrm{diam}(G)\left(\Delta(G)-1\right)$. In the coloring
$\alpha$ of $G$, we consider the edges with colors $1$ and
$2+\mathrm{diam}(G)\left(\Delta(G)-1\right)$. Let
$e=u_{1}u_{2},e^{\prime}=w_{1}w_{2}$ and
$\alpha(e)=1,\alpha(e^{\prime})=2+\mathrm{diam}(G)\left(\Delta(G)-1\right)$.
Since for any two edges in a bipartite graph $G$, some two of their endpoints
must be at a distance of at most $\mathrm{diam}(G)-1$ from each other, we may
assume that there is the path $P$ joining $e$ and $e^{\prime}$ with the length
is not greater than $\mathrm{diam}(G)-1$. Also, we may assume that $P$ joining
$e$ with $e^{\prime}$ joins $u_{1}$ with $w_{1}$, where

$P=\left(v_{0},e_{1},v_{1},\ldots,v_{i-1},e_{i},v_{i},\ldots,v_{k-1},e_{k},v_{k}\right)$
and $v_{0}=u_{1}$, $v_{k}=w_{1}$.

Since $\alpha$ is an interval cyclic coloring of $G$, for $1\leq i\leq k$, we
have

either $\alpha(v_{i-1}v_{i})\leq
1+{\sum\limits_{j=0}^{i-1}\left(d_{G}(v_{j})-1\right)}$ or
$\alpha(v_{i-1}v_{i})\geq
W_{c}(G)+1-{\sum\limits_{j=0}^{i-1}\left(d_{G}(v_{j})-1\right)}$.

From this, we have either

$\alpha(e^{\prime})\leq 1+{\sum\limits_{j=0}^{k}\left(d_{G}(v_{j})-1\right)}$
(3)

or

$\alpha(e^{\prime})\geq
W_{c}(G)+1-{\sum\limits_{j=0}^{k}\left(d_{G}(v_{j})-1\right)}.$ (4)

On the other hand, by (3) and taking into account that
$k\leq\mathrm{diam}(G)-1$, we obtain

$2+\mathrm{diam}(G)\left(\Delta(G)-1\right)=\alpha(e^{\prime})\leq
1+{\sum\limits_{j=0}^{k}\left(d_{G}(v_{j})-1\right)}\leq
1+\mathrm{diam}(G)\left(\Delta(G)-1\right)$, which is a contradiction.

Similarly, by (4) and taking into account that $k\leq\mathrm{diam}(G)-1$, we
obtain

$2+\mathrm{diam}(G)\left(\Delta(G)-1\right)=\alpha(e^{\prime})\geq
W_{c}(G)+1-{\sum\limits_{j=0}^{k}\left(d_{G}(v_{j})-1\right)}\geq
W_{c}(G)+1-\mathrm{diam}(G)\left(\Delta(G)-1\right)$ and thus $W_{c}(G)\leq
1+2\cdot\mathrm{diam}(G)\left(\Delta(G)-1\right)$, which is a contradiction.
$\square$

Now we show that the coefficient 2 in the last upper bounds cannot be
improved.

###### Theorem 17

For any integers $d\geq 2$ and $n\geq 3$, there exists a connected graph $G$
with $\Delta(G)=d$ and
$\mathrm{diam}(G)=\left\lfloor\frac{n}{2}\right\rfloor+2$ such that
$G\in\mathfrak{N}_{c}$ and $W_{c}(G)=n(d-1)$.

  * Proof.

For the proof, we construct a graph $G_{d,n}$ that satisfies the specified
conditions. We define a graph $G_{d,n}$ as follows:

$V(G_{d,n})=\\{v_{1},\ldots,v_{n}\\}\cup\left\\{u^{(i)}_{j}\colon\,1\leq i\leq
n,1\leq j\leq d-2\right\\}$ and

$E(G_{d,n})=\\{v_{i}v_{i+1}\colon\,1\leq i\leq
n-1\\}\cup\left\\{v_{1}v_{n}\right\\}\cup\left\\{v_{i}u^{(i)}_{j}\colon\,1\leq
i\leq n,1\leq j\leq d-2\right\\}$.

Clearly, $G_{d,n}$ is a connected graph with $\Delta(G_{d,n})=d$ and
$\mathrm{diam}(G_{d,n})=\left\lfloor\frac{n}{2}\right\rfloor+2$.

Let us show that $G_{d,n}$ has an interval cyclic $n(d-1)$-coloring.

Define an edge-coloring $\alpha$ of $G_{d,n}$ as follows:

(1)

for $1\leq i\leq n$ and $1\leq j\leq d-2$, let

$\alpha\left(v_{i}u^{(i)}_{j}\right)=(i-1)(d-1)+j$;

(2)

for $1\leq i\leq n-1$, let

$\alpha\left(v_{i}v_{i+1}\right)=i(d-1)$ and
$\alpha\left(v_{1}v_{n}\right)=n(d-1)$.

It is easy to see that $\alpha$ is an interval cyclic $n(d-1)$-coloring of
$G_{d,n}$. This implies that $G_{d,n}\in\mathfrak{N}_{c}$ and
$W_{c}(G_{d,n})\geq n(d-1)$. On the other hand, clearly
$W_{c}(G_{d,n})\leq|E(G_{d,n})|=n(d-1)$ and thus $W_{c}(G_{d,n})=n(d-1)$.
$\square$

In the last part of the section we investigate the feasible sets of interval
cyclically colorable graphs.

###### Theorem 18

If $G\in\mathfrak{N}$, then $G\in\mathfrak{N}_{c}$ and
$\left[\Delta(G),W(G)\right]\subseteq F(G)$.

  * Proof.

Since any interval $t$-coloring of $G$ is also an interval cyclic $t$-coloring
of $G$, we obtain that $G\in\mathfrak{N}_{c}$.

Assume that $\Delta(G)\leq t\leq W(G)$. Let $\alpha$ be an interval
$W(G)$-coloring of $G$. Define an edge-coloring $\beta$ of $G$ as follows: for
every $e\in E(G)$, let

$\beta(e)=\left\\{\begin{tabular}[]{ll}$\alpha(e)\pmod{t}$,&if
$\alpha(e)\pmod{t}\neq 0$,\\\ $t$,&otherwise.\\\ \end{tabular}\right.$

It is easy to see that $\beta$ is an interval cyclic $t$-coloring of $G$.
$\square$

###### Corollary 19

([23]). If $G\in\mathfrak{N}$, then $G\in\mathfrak{N}_{c}$ and
$w_{c}(G)=\Delta(G)$.

###### Theorem 20

If $G$ is an Eulerian graph and $|E(G)|$ is odd, then $G$ has no interval
cyclic $t$-coloring for every even positive integer $t$.

  * Proof.

Suppose, to the contrary, that $G$ has an interval cyclic $t$-coloring
$\alpha$ for some even positive integer $t$. Since $G$ is an Eulerian graph,
$G$ is connected and $d_{G}(v)$ is even for any $v\in V(G)$, by Euler’s
Theorem. Since $\alpha$ is an interval cyclic coloring and all degrees of
vertices of $G$ are even, we have that for any $v\in V(G)$, the set
$S\left(v,\alpha\right)$ contains exactly $\frac{d_{G}(v)}{2}$ even colors and
$\frac{d_{G}(v)}{2}$ odd colors. Now let $m_{odd}$ be the number of edges with
odd colors in the coloring $\alpha$. By Handshaking lemma, we obtain
$m_{odd}=\frac{1}{2}\sum\limits_{v\in
V(G)}\frac{d_{G}(v)}{2}=\frac{|E(G)|}{2}$. Thus $|E(G)|$ is even, which is a
contradiction. $\square$

###### Corollary 21

If $G$ is an interval cyclically colorable Eulerian graph with an odd number
of edges and $\chi^{\prime}(G)=\Delta(G)$, then $w_{c}(G)>\chi^{\prime}(G)$.

Figure 2: Interval cyclic $5$-colorings of $K_{1,1,3}$ and $F$.

Fig. 2 shows the complete tripartite graph $K_{1,1,3}$ and the fish graph $F$
that are smallest interval cyclically colorable Eulerian graphs with an odd
number of edges and for which the chromatic index is equal to the maximum
degree. Clearly, $\chi^{\prime}(K_{1,1,3})=\chi^{\prime}(F)=4$, but
$w_{c}(K_{1,1,3})=w_{c}(F)=5$.

Finally let us consider the simple path $P_{m}$ and the simple cycle $C_{n}$
($n\geq 3$). Clearly, $P_{m}\in\mathfrak{N}_{c}$ and
$w_{c}(P_{m})=\Delta(P_{m})$, $W_{c}(P_{m})=m-1$. Moreover,
$F(P_{m})=\left[w_{c}(P_{m}),W_{c}(P_{m})\right]$, so the feasible set of
$P_{m}$ is gap-free. Now let us consider the simple cycle $C_{n}$. Clearly,
$C_{n}\in\mathfrak{N}_{c}$ and $w_{c}(C_{n})=\chi^{\prime}(C_{n})$,
$W_{c}(C_{n})=n$. Moreover, it is not difficult to see that any simple cycle
with an odd number of vertices has an interval cyclic $t$-coloring for every
odd integer $t$, $3\leq t\leq n$, so, by Theorem 20, we obtain

###### Corollary 22

For any odd integer $n\geq 3$, we have $F(C_{n})=\left[3,n\right]_{odd}$.

This corollary implies that for any odd integer $n\geq 5$, the feasible set of
$C_{n}$ is not gap-free. A more general result on the feasible set of simple
cycles was obtained by Kamalian in [15].

###### Theorem 23

([15]). For any integer $n\geq 3$, we have

$F(C_{n})=\left\\{\begin{tabular}[]{ll}$\left[3,n\right]_{odd}$,&if $n$ is
odd,\\\
$\left[2,\frac{n}{2}+1\right]\cup\left[\frac{n}{2}+2,n\right]_{even}$,&if
$n=4k,k\in\mathbb{N}$,\\\
$\left[2,\frac{n}{2}+1\right]\cup\left[\frac{n}{2}+3,n\right]_{even}$,&if
$n=4k+2,k\in\mathbb{N}$.\\\ \end{tabular}\right.$

##  4 Interval cyclic edge-colorings of complete graphs

This section is devoted to interval cyclic colorings of complete graphs. In
[31], Vizing proved the following

###### Theorem 24

For the complete graph $K_{n}$ ($n\geq 2$), we have

$\chi^{\prime}(K_{n})=\left\\{\begin{tabular}[]{ll}$n-1$,&if $n$ is even,\\\
$n$,&if $n$ is odd.\\\ \end{tabular}\right.$

From Corollary 6 and Theorem 24, we obtain that if $n\in\mathbb{N}$, then
$K_{2n},K_{2n+1}\in\mathfrak{N}_{c}$ and
$w_{c}(K_{2n})=2n-1,w_{c}(K_{2n+1})=2n+1$. Now let us consider the parameters
$W_{c}(K_{2n})$ and $W_{c}(K_{2n+1})$ when $n\in\mathbb{N}$. In [24],
Petrosyan investigated interval colorings of complete graphs and hypercubes.
In particular, he proved the following

###### Theorem 25

If $n=p2^{q}$, where $p$ is odd and $q$ is nonnegative, then

$W(K_{2n})\geq 4n-2-p-q$.

Moreover, if $2n-1\leq t\leq 4n-2-p-q$, then $K_{2n}$ has an interval
$t$-coloring.

###### Corollary 26

If $n=p2^{q}$, where $p$ is odd and $q$ is nonnegative, then

$W_{c}(K_{2n})\geq 4n-2-p-q$.

Moreover, $\left[2n-1,4n-2-p-q\right]\subseteq F(K_{2n})$.

Figure 3: The interval cyclic $9$-coloring of $K_{6}$ and the interval cyclic
$12$-coloring of $K_{8}$.

On the other hand, Corollary 13 implies that $W_{c}(K_{2n})\leq 6n-6$ for
$n\geq 2$. It is not difficult to see that $W(K_{4})=W_{c}(K_{4})=4$. In [24],
it was proved that $W(K_{6})=7$ and $W(K_{8})=11$, but Fig. 3 shows that
$W_{c}(K_{6})\geq 9$ and $W(K_{8})\geq 12$, so $W_{c}(K_{6})>W(K_{6})$ and
$W_{c}(K_{8})>W(K_{8})$. In general, we strongly believe that
$W_{c}(K_{2n})>W(K_{2n})$ for $n\geq 3$. Now we give a lower bound for
$W_{c}(K_{2n+1})$ when $n\in\mathbb{N}$.

###### Theorem 27

If $n\in\mathbb{N}$, then $W_{c}(K_{2n+1})\geq 3n$.

  * Proof.

For the proof, it suffices to construct an interval cyclic $3n$-coloring of
$K_{2n+1}$. Let $V(K_{2n+1})=\left\\{v_{0},v_{1},\ldots,v_{2n}\right\\}$.

Define an edge-coloring $\beta$ of $K_{2n+1}$. For each edge $v_{i}v_{j}\in
E(K_{2n+1})$ with $i<j$, define a color $\beta\left(v_{i}v_{j}\right)$ as
follows:

$\beta\left(v_{i}v_{j}\right)=\left\\{\begin{tabular}[]{ll}$1$,&if $i=0$,
$j=1$;\\\ $2n+1$,&if $i=0$, $j=2$;\\\ $j-1$,&if $i=0$, $3\leq j\leq n$;\\\
$n+1+j$,&if $i=0$, $n+1\leq j\leq 2n-2$;\\\ $n$,&if $i=0$, $j=2n-1$;\\\
$3n$,&if $i=0$, $j=2n$;\\\ $i+j-1$,&if $1\leq
i\leq\left\lfloor\frac{n}{2}\right\rfloor$, $2\leq j\leq n$, $i+j\leq n+1$;\\\
$i+j+n-2$,&if $2\leq i\leq n-1$, $\left\lfloor\frac{n}{2}\right\rfloor+2\leq
j\leq n$, $i+j\geq n+2$;\\\ $n+1+j-i$,&if $3\leq i\leq n$, $n+1\leq j\leq
2n-2$, $j-i\leq n-2$;\\\ $j-i+1$,&if $1\leq i\leq n$, $n+1\leq j\leq 2n$,
$j-i\geq n$;\\\ $2i-1$,&if $2\leq i\leq
1+\left\lfloor\frac{n-1}{2}\right\rfloor$, $n+1\leq j\leq
n+\left\lfloor\frac{n-1}{2}\right\rfloor$, $j-i=n-1$;\\\ $i+j-1$,&if
$\left\lfloor\frac{n-1}{2}\right\rfloor+2\leq i\leq n$,
$n+1+\left\lfloor\frac{n-1}{2}\right\rfloor\leq j\leq 2n-1$, $j-i=n-1$;\\\
$i+j-2n+1$,&if $n+1\leq i\leq n+\left\lfloor\frac{n}{2}\right\rfloor-1$,
$n+2\leq j\leq 2n-2$, $i+j\leq 3n-1$;\\\ $i+j-n$,&if $n+1\leq i\leq 2n-1$,
$n+\left\lfloor\frac{n}{2}\right\rfloor+1\leq j\leq 2n$, $i+j\geq
3n$.\end{tabular}\right.$

Let us prove that $\beta$ is an interval cyclic $3n$-coloring of $K_{2n+1}$.

Let $G$ be the subgraph of $K_{2n+1}$ induced by $\\{v_{1},\ldots,v_{2n}\\}$.
Clearly, $G$ is isomorphic to $K_{2n}$. This edge-coloring $\beta$ of
$K_{2n+1}$ is constructed and based on the interval $(3n-2)$-coloring of $G$
which is described in the proof of Theorem 4 from [24]. We use this interval
$(3n-2)$-coloring of $G$ and then we shift all colors of the edges of $G$ by
one. Let $\alpha$ be this edge-coloring of $G$. Using the property of this
edge-coloring which is described in the proof of Corollary 6 from [24], we get

1)

$S\left(v_{1},\alpha\right)=S\left(v_{2},\alpha\right)=[2,2n]$,

2)

$S\left(v_{i},\alpha\right)=S\left(v_{n+i-2},\alpha\right)=[i,2n-2+i]$ for
$3\leq i\leq n$,

3)

$S\left(v_{2n-1},\alpha\right)=S\left(v_{2n},\alpha\right)=[n+1,3n-1]$.

Now, by the definition of $\beta$, we have

1)

$S\left(v_{0},\beta\right)=[1,n]\cup[2n+1,3n]$,

2)

$S\left(v_{1},\beta\right)=[1,2n]$ and $S\left(v_{2},\beta\right)=[2,2n+1]$,

3)

$S\left(v_{i},\beta\right)=[i-1,2n-2+i]$ and
$S\left(v_{n+i-2},\beta\right)=[i,2n-1+i]$ for $3\leq i\leq n$,

4)

$S\left(v_{2n-1},\beta\right)=[n,3n-1]$ and
$S\left(v_{2n},\beta\right)=[n+1,3n]$.

This shows that $\beta$ is an interval cyclic $3n$-coloring of $K_{2n+1}$ and
hence $W_{c}(K_{2n+1})\geq 3n$. $\square$

Note that the lower bound in Theorem 27 is sharp for $K_{3}$, since
$W_{c}(K_{3})=3$. On the other hand, Corollary 13 implies that
$W_{c}(K_{2n+1})\leq 6n-3$ for $n\in\mathbb{N}$. It is worth also noting that,
in general, the feasible set of $K_{2n+1}$ is not gap-free. For example,
$K_{7}$ has an interval cyclic $7$-coloring and, by Theorem 27, it also has an
interval cyclic $9$-coloring, but since $|E\left(K_{7}\right)|=21$, Theorem 20
implies that $K_{7}$ has no interval cyclic $8$-coloring, so $F(K_{7})$ is not
gap-free.

##  5 Interval cyclic edge-colorings of complete bipartite and tripartite
graphs

In this section we show that all complete bipartite and tripartite graphs are
interval cyclically colorable. We also obtain some bounds for parameters
$W_{c}\left(K_{m,n}\right)$ and $w_{c}\left(K_{l,m,n}\right)$ when
$l,m,n\in\mathbb{N}$. In [12], Kamalian investigated interval colorings of
complete bipartite graphs and trees. In particular, he proved the following

###### Theorem 28

For any $m,n\in\mathbb{N}$, we have

(1)

$K_{m,n}\in\mathfrak{N}$,

(2)

$w\left(K_{m,n}\right)=m+n-\gcd(m,n)$,

(3)

$W\left(K_{m,n}\right)=m+n-1$,

(4)

if $w\left(K_{m,n}\right)\leq t\leq W\left(K_{m,n}\right)$, then $K_{m,n}$ has
an interval $t$-coloring.

We first prove the theorem on the feasible set of complete bipartite graphs.

###### Theorem 29

If $\min\\{m,n\\}=1$, then $w_{c}(K_{m,n})=W_{c}(K_{m,n})=m+n-1$. If
$\min\\{m,n\\}\geq 2$, then $\left[\max\\{m,n\\},m+n\right]\subseteq
F\left(K_{m,n}\right)$.

  * Proof.

First note that if $\min\\{m,n\\}=1$, then $K_{m,n}$ is a star and hence
$w_{c}(K_{m,n})=W_{c}(K_{m,n})=m+n-1$.

Assume that $\min\\{m,n\\}\geq 2$. Let us show that if $\max\\{m,n\\}\leq
t\leq m+n$, then $K_{m,n}$ has an interval cyclic $t$-coloring. By Theorems 18
and 28, we have $\left[\max\\{m,n\\},m+n-1\right]\subseteq
F\left(K_{m,n}\right)$. Now we prove that $K_{m,n}$ has an interval cyclic
$(m+n)$-coloring.

Let $V(K_{m,n})=\\{u_{1},\ldots,u_{m},v_{1},\ldots,v_{n}\\}$ and
$E(K_{m,n})=\left\\{u_{i}v_{j}\colon\,1\leq i\leq m,1\leq j\leq n\right\\}$.

Define an edge-coloring $\alpha$ of $K_{m,n}$ as follows: for $1\leq i\leq m$
and $1\leq j\leq n$, let

$\alpha\left(u_{i}v_{j}\right)=\left\\{\begin{tabular}[]{ll}$i+j-1$,&if
$(i,j)\neq(1,n)$,\\\ $m+n$,&otherwise.\\\ \end{tabular}\right.$

It is not difficult to see that $\alpha$ is an interval cyclic
$(m+n)$-coloring of $K_{m,n}$ and hence
$\left[\max\\{m,n\\},m+n\right]\subseteq F\left(K_{m,n}\right)$ when
$\min\\{m,n\\}\geq 2$. $\square$

###### Corollary 30

If $\min\\{m,n\\}=1$, then $w_{c}(K_{m,n})=W_{c}(K_{m,n})=m+n-1$. If
$\min\\{m,n\\}\geq 2$, then $w_{c}(K_{m,n})=\max\\{m,n\\}$ and
$W_{c}(K_{m,n})\geq m+n$.

Now we show that all complete tripartite graphs are interval cyclically
colorable.

###### Theorem 31

For any $l,m,n\in\mathbb{N}$, we have $K_{l,m,n}\in\mathfrak{N}_{c}$ and
$w_{c}(K_{l,m,n})\leq l+m+n$.

  * Proof.

Without loss of generality we may assume that $l\leq m\leq n$. Clearly, for
the proof, it suffices to construct an interval cyclic $(l+m+n)$-coloring of
$K_{l,m,n}$.

Let
$V(K_{l,m,n})=\\{u_{1},\ldots,u_{m},v_{1},\ldots,v_{n},w_{1},\ldots,w_{l}\\}$
and $E(K_{l,m,n})=\left\\{u_{i}v_{j}\colon\,1\leq i\leq m,1\leq j\leq
n\right\\}\cup\left\\{u_{i}w_{j}\colon\,1\leq i\leq m,1\leq j\leq
l\right\\}\cup\left\\{w_{i}v_{j}\colon\,1\leq i\leq l,1\leq j\leq n\right\\}$.

Define an edge-coloring $\alpha$ of $K_{l,m,n}$ as follows:

(1)

for $1\leq i\leq m$ and $1\leq j\leq n$, let

$\alpha\left(u_{i}v_{j}\right)=l+i+j-1$;

(2)

for $1\leq i\leq l$ and $1\leq j\leq n$, let

$\alpha\left(w_{i}v_{j}\right)=i+j-1$;

(3)

for $1\leq i\leq m$, $1\leq j\leq l$ and $i+j\leq m+1$, let

$\alpha\left(u_{i}w_{j}\right)=l+n+i+j-1$;

(4)

for $1\leq i\leq m$, $1\leq j\leq l$ and $i+j\geq m+2$, let

$\alpha\left(u_{i}w_{j}\right)=i+j-m-1$.

Let us prove that $\alpha$ is an interval cyclic $(l+m+n)$-coloring of
$K_{l,m,n}$.

By the definition of $\alpha$, we have

1)

for $1\leq i\leq m-l+1$,

$S\left(u_{i},\alpha\right)=[l+i,l+n+i-1]\cup[l+n+i,2l+n+i-1]=[l+i,2l+n+i-1]$
due to (1) and (3),

2)

for $m-l+2\leq i\leq m$,

$S\left(u_{i},\alpha\right)=[l+i,l+n+i-1]\cup[l+n+i,l+m+n]\cup[1,l-m-1+i]=[1,l-m-1+i]\cup[l+i,l+m+n]$
due to (1),(3) and (4),

3)

for $1\leq i\leq n$,

$S\left(v_{i},\alpha\right)=[l+i,l+m+i-1]\cup[i,l+i-1]=[i,l+m+i-1]$ due to (1)
and (2),

4)

for $1\leq i\leq l$,

$S\left(w_{i},\alpha\right)=[i,n+i-1]\cup[l+n+i,l+m+n]\cup[1,i-1]=[1,n+i-1]\cup[l+n+i,l+m+n]$
due to (2),(3) and (4).

This implies that $\alpha$ is an interval cyclic $(l+m+n)$-coloring of
$K_{l,m,n}$; thus $K_{l,m,n}\in\mathfrak{N}_{c}$ and
$w_{c}\left(K_{l,m,n}\right)\leq l+m+n$ for $l,m,n\in\mathbb{N}$. $\square$

###### Corollary 32

For any $l,m,n\in\mathbb{N}$, we have $K_{l,m,n}\in\mathfrak{N}_{c}$ and
$W_{c}(K_{l,m,n})\geq l+m+n$.

Note that the upper bound in Theorem 31 is sharp for $K_{1,m,n}$ when $m$ and
$n$ are odd, since
$w_{c}\left(K_{1,1,1}\right)=\chi^{\prime}\left(C_{3}\right)=3$ and for
$\max\\{m,n\\}\geq 3$, $m+n+1\geq
w_{c}\left(K_{1,m,n}\right)>\chi^{\prime}\left(K_{1,m,n}\right)=\Delta\left(K_{1,m,n}\right)=m+n$
due to Corollary 21. It is worth also noting that although all complete
tripartite graphs are interval cyclically colorable, in [9] Grzesik and
Khachatrian proved that $K_{1,m,n}$ is interval colorable if and only if
$\gcd(m+1,n+1)=1$. This implies that there are infinitely many complete
tripartite graphs from the class $\mathfrak{N}_{c}\setminus\mathfrak{N}$.

##  6 Interval cyclic edge-colorings of hypercubes

In this section we show that hypercubes $Q_{n}$ are interval cyclically
colorable. We also obtain some bounds for the parameter
$W_{c}\left(Q_{n}\right)$ when $n\in\mathbb{N}$. In [24], Petrosyan
investigated interval colorings of complete graphs and hypercubes. In
particular, he proved that $Q_{n}\in\mathfrak{N}$ and $w(Q_{n})=n$,
$W(Q_{n})\geq\frac{n(n+1)}{2}$ for any $n\in\mathbf{N}$. In the same paper he
also conjectured that $W(Q_{n})=\frac{n(n+1)}{2}$ for any $n\in\mathbf{N}$. In
[26], the authors confirmed this conjecture. This implies that
$Q_{n}\in\mathfrak{N}_{c}$ and $w_{c}(Q_{n})=n$,
$W_{c}(Q_{n})\geq\frac{n(n+1)}{2}$. Moreover, by Theorem 18, we obtain
$\left[n,\frac{n(n+1)}{2}\right]\subseteq F(Q_{n})$. On the other hand, since
$Q_{n}$ is a connected bipartite graph and taking into account that
$\mathrm{diam}\left(Q_{n}\right)=\Delta\left(Q_{n}\right)=n$, we get
$W_{c}\left(Q_{n}\right)\leq
1+2\cdot\mathrm{diam}\left(Q_{n}\right)\left(\Delta\left(Q_{n}\right)-1\right)=2n^{2}-2n+1$,
by Theorem 16. So, we have $\frac{n(n+1)}{2}\leq W_{c}\left(Q_{n}\right)\leq
2n^{2}-2n+1$ for any $n\in\mathbf{N}$. Now we prove a new lower bound for
$W_{c}\left(Q_{n}\right)$ which improves $W_{c}(Q_{n})\geq\frac{n(n+1)}{2}$
for $2\leq n\leq 5$.

Figure 4: The interval cyclic $8$-coloring of $Q_{3}$.

###### Theorem 33

For any integer $n\geq 2$, we have $W_{c}\left(Q_{n}\right)\geq 4(n-1)$.

  * Proof.

First let us note that for any integer $n\geq 2$, $Q_{n}$ has an interval
$(n+1)$-coloring such that for one half of vertices of $Q_{n}$, the set of
colors appearing on edges incident to these vertices is an interval $[1,n]$
and for remaining half of vertices of $Q_{n}$, the set of colors appearing on
edges incident to these remaining vertices is an interval $[2,n+1]$. It can be
easily done by induction on $n$. Also, it is not difficult to see that
$W_{c}\left(Q_{2}\right)=W_{c}\left(C_{4}\right)=4$ and
$W_{c}\left(Q_{3}\right)\geq 8$ (See Fig. 4).

Assume that $n\geq 4$.

For $(i,j)\in\\{0,1\\}^{2}$, let $Q_{n-2}^{(i,j)}$ be the subgraph of $Q_{n}$
induced by the vertices

$\left\\{\left(i,j,\alpha_{3},\ldots,\alpha_{n}\right)\colon\,\left(\alpha_{3},\ldots,\alpha_{n}\right)\in\left\\{0,1\right\\}^{n-2}\right\\}$.

Each $Q_{n-2}^{(i,j)}$ is isomorphic to $Q_{n-2}$. Let $\varphi$ be an
interval $(n-1)$-coloring of $Q_{n-2}^{(0,0)}$ such that for one half of
vertices of $Q_{n-2}^{(0,0)}$, the set of colors appearing on edges incident
to these vertices be an interval $[1,n-2]$ and for remaining half of vertices
of $Q_{n-2}^{(0,0)}$, the set of colors appearing on edges incident to these
remaining vertices be an interval $[2,n-1]$.

Let us define an edge-coloring $\psi$ of subgraphs $Q_{n-2}^{(0,1)}$,
$Q_{n-2}^{(1,1)}$ and $Q_{n-2}^{(1,0)}$ of $Q_{n}$ as follows:

(1)

for every edge $\left(0,1,\bar{\alpha}\right)\left(0,1,\bar{\beta}\right)\in
E\left(Q_{n-2}^{(0,1)}\right)$, let

$\psi\left(\left(0,1,\bar{\alpha}\right)\left(0,1,\bar{\beta}\right)\right)=\varphi\left(\left(0,0,\bar{\alpha}\right)\left(0,0,\bar{\beta}\right)\right)+n-1$;

(2)

for every edge $\left(1,1,\bar{\alpha}\right)\left(1,1,\bar{\beta}\right)\in
E\left(Q_{n-2}^{(1,1)}\right)$, let

$\psi\left(\left(1,1,\bar{\alpha}\right)\left(1,1,\bar{\beta}\right)\right)=\varphi\left(\left(0,0,\bar{\alpha}\right)\left(0,0,\bar{\beta}\right)\right)+2n-2$;

(3)

for every edge $\left(1,0,\bar{\alpha}\right)\left(1,0,\bar{\beta}\right)\in
E\left(Q_{n-2}^{(1,0)}\right)$, let

$\psi\left(\left(1,0,\bar{\alpha}\right)\left(1,0,\bar{\beta}\right)\right)=\varphi\left(\left(0,0,\bar{\alpha}\right)\left(0,0,\bar{\beta}\right)\right)+3n-3$.

Now we define an edge-coloring $\lambda$ of the graph $Q_{n}$.

For every edge $\tilde{\alpha}\tilde{\beta}\in E\left(Q_{n}\right)$, let

$\lambda\left(\tilde{\alpha}\tilde{\beta}\right)=\left\\{\begin{tabular}[]{ll}$\varphi\left(\tilde{\alpha}\tilde{\beta}\right),$&if
$\tilde{\alpha},\tilde{\beta}\in V\left(Q_{n-2}^{(0,0)}\right)$,\\\
$\psi\left(\tilde{\alpha}\tilde{\beta}\right),$&if
$\tilde{\alpha},\tilde{\beta}\in V\left(Q_{n-2}^{(0,1)}\right)$ or
$\tilde{\alpha},\tilde{\beta}\in V\left(Q_{n-2}^{(1,1)}\right)$ or
$\tilde{\alpha},\tilde{\beta}\in V\left(Q_{n-2}^{(1,0)}\right)$,\\\ $n-1,$&if
$\tilde{\alpha}\in V\left(Q_{n-2}^{(0,0)}\right)$, $\tilde{\beta}\in
V\left(Q_{n-2}^{(0,1)}\right)$,
$S\left(\tilde{\alpha},\varphi\right)=[1,n-2]$,\\\ $n,$&if $\tilde{\alpha}\in
V\left(Q_{n-2}^{(0,0)}\right)$, $\tilde{\beta}\in
V\left(Q_{n-2}^{(0,1)}\right)$,
$S\left(\tilde{\alpha},\varphi\right)=[2,n-1]$,\\\ $2n-2,$&if
$\tilde{\alpha}\in V\left(Q_{n-2}^{(0,1)}\right)$, $\tilde{\beta}\in
V\left(Q_{n-2}^{(1,1)}\right)$,
$S\left(\tilde{\alpha},\psi\right)=[n,2n-3]$,\\\ $2n-1,$&if $\tilde{\alpha}\in
V\left(Q_{n-2}^{(0,1)}\right)$, $\tilde{\beta}\in
V\left(Q_{n-2}^{(1,1)}\right)$,
$S\left(\tilde{\alpha},\psi\right)=[n+1,2n-2]$,\\\ $3n-3,$&if
$\tilde{\alpha}\in V\left(Q_{n-2}^{(1,1)}\right)$, $\tilde{\beta}\in
V\left(Q_{n-2}^{(1,0)}\right)$,
$S\left(\tilde{\alpha},\psi\right)=[2n-1,3n-4]$,\\\ $3n-2,$&if
$\tilde{\alpha}\in V\left(Q_{n-2}^{(1,1)}\right)$, $\tilde{\beta}\in
V\left(Q_{n-2}^{(1,0)}\right)$,
$S\left(\tilde{\alpha},\psi\right)=[2n,3n-3]$,\\\ $4n-4,$&if
$\tilde{\alpha}\in V\left(Q_{n-2}^{(1,0)}\right)$, $\tilde{\beta}\in
V\left(Q_{n-2}^{(0,0)}\right)$,
$S\left(\tilde{\alpha},\psi\right)=[3n-2,4n-5]$,\\\ $1,$&if $\tilde{\alpha}\in
V\left(Q_{n-2}^{(1,0)}\right)$, $\tilde{\beta}\in
V\left(Q_{n-2}^{(0,0)}\right)$,
$S\left(\tilde{\alpha},\psi\right)=[3n-1,4n-4]$.\end{tabular}\right.$

It is easy to verify that $\lambda$ is an interval cyclic $(4n-4)$-coloring of
$Q_{n}$; thus $W_{c}\left(Q_{n}\right)\geq 4(n-1)$ for $n\geq 2$. $\square$

This theorem implies that
$W_{c}\left(Q_{2}\right)=4,W_{c}\left(Q_{3}\right)\geq
8,W_{c}\left(Q_{4}\right)\geq 12$ and $W_{c}\left(Q_{5}\right)\geq 16$.
Moreover, it is not difficult to see that $F\left(Q_{2}\right)=[2,4]$,
$F\left(Q_{3}\right)=[3,8]$, $[4,12]\subseteq F\left(Q_{4}\right)$ and
$[5,16]\subseteq F\left(Q_{5}\right)$. We strongly believe that the feasible
set of $Q_{n}$ is gap-free, but this is an open problem.

##  7 Graphs that have no interval cyclic edge-coloring

In this section we describe two methods for constructing of interval
cyclically non-colorable graphs. Our first method is based on trees and it was
earlier used for constructing of interval non-colorable graphs in [28].

Let $T$ be a tree and $V(T)=\\{v_{1},\ldots,v_{n}\\}$, $n\geq 2$. Let
$P(v_{i},v_{j})$ be a simple path joining $v_{i}$ and $v_{j}$ in $T$,
$VP(v_{i},v_{j})$ and $EP(v_{i},v_{j})$ denote the sets of vertices and edges
of this path, respectively. Also, let $L(T)=\\{v\colon\,v\in V(T)\wedge
d_{T}(v)=1\\}$. For a simple path $P(v_{i},v_{j})$, define $LP(v_{i},v_{j})$
as follows:

$LP(v_{i},v_{j})=|EP(v_{i},v_{j})|+|\left\\{vw\colon\,vw\in E(T),v\in
VP(v_{i},v_{j}),w\notin VP(v_{i},v_{j})\right\\}|$.

Define: $M(T)={\max}_{1\leq i<j\leq n}LP(v_{i},v_{j})$. Let us define the
graph $\widetilde{T}$ as follows:

$V(\widetilde{T})=V(T)\cup\\{u\\}$, $u\notin V(T)$,
$E(\widetilde{T})=E(T)\cup\\{uv\colon\,v\in L(T)\\}$.

Clearly, $\widetilde{T}$ is a connected graph with
$\Delta(\widetilde{T})=|L(T)|$. Moreover, if $T$ is a tree in which the
distance between any two pendant vertices is even, then $\widetilde{T}$ is a
connected bipartite graph.

In [14], Kamalian proved the following result.

###### Theorem 34

If $T$ is a tree, then

(1)

$T\in\mathfrak{N}_{c}$,

(2)

$w_{c}(T)=\Delta(G)$,

(3)

$W_{c}(T)=M(T)$,

(4)

$F(T)=[w_{c}(T),W_{c}(T)]$.

###### Theorem 35

If $T$ is a tree and $|L(T)|\geq 2(M(T)+2)$, then
$\widetilde{T}\notin\mathfrak{N}_{c}$.

  * Proof.

Suppose, to the contrary, that $\widetilde{T}$ has an interval cyclic
$t$-coloring $\alpha$ for some $t\geq|L(T)|$.

Consider the vertex $u$. Without loss of generality we may assume that
$S(u,\alpha)=[1,|L(T)|]$. Let $v$ and $v^{\prime}$ be two vertices adjacent to
$u$ such that $\alpha(uv)=1$ and $\alpha(uv^{\prime})=M(T)+3$. Since
$\widetilde{T}-u$ is a tree, there is a unique path $P(v,v^{\prime})$ in
$\widetilde{T}-u$ joining $v$ with $v^{\prime}$, where

$P(v,v^{\prime})=(x_{0},e_{1},x_{1},\ldots,x_{i-1},e_{i},x_{i},\ldots,x_{k-1},e_{k},x_{k})$,
$x_{0}=v$, $x_{k}=v^{\prime}$.

Since $\alpha$ is an interval cyclic coloring of $G$, for $1\leq i\leq k$, we
have

either $\alpha(x_{i-1}x_{i})\leq
2+{\sum\limits_{j=0}^{i-1}\left(d_{T}(x_{j})-1\right)}$ or
$\alpha(x_{i-1}x_{i})\geq
t-{\sum\limits_{j=0}^{i-1}\left(d_{T}(x_{j})-1\right)}$.

From this, we have either

$\alpha(x_{k-1}x_{k})=\alpha(x_{k-1}v^{\prime})\leq
2+{\sum\limits_{j=0}^{k-1}\left(d_{T}(v_{j})-1\right)}=1+LP(v,v^{\prime})\leq
1+M(T)$ (5)

or

$\alpha(x_{k-1}x_{k})=\alpha(x_{k-1}v^{\prime})\geq
t-{\sum\limits_{j=0}^{k-1}\left(d_{T}(v_{j})-1\right)}=t+1-LP(v,v^{\prime})\geq
t+1-M(T).$ (6)

On the other hand, by (5), we obtain $M(T)+3=\alpha(uv^{\prime})\leq 2+M(T)$,
which is a contradiction. Similarly, by (6), we obtain
$M(T)+3=\alpha(uv^{\prime})\geq t-M(T)$ and thus $t\leq 2M(T)+3$, which is a
contradiction. $\square$

###### Corollary 36

If $T$ is a tree in which the distance between any two pendant vertices is
even and $|L(T)|\geq 2(M(T)+2)$, then the bipartite graph $\widetilde{T}$ has
no interval cyclic coloring.

Figure 5: The tree $T$.

Now let us consider the tree $T$ shown in Fig. 5. Since $M(T)=18$ and
$|L(T)|=40$, the bipartite graph $\widetilde{T}$ with $|V(\widetilde{T})|=50$
and $\Delta(\widetilde{T})=40$ has no interval cyclic coloring.

The second method which we consider is based on complete graphs and it was
first described in [23], but here we prove a more stronger result.

Let $K_{2n+1}$ be a complete graph on $2n+1$ vertices and
$V(K_{2n+1})=\left\\{v_{1},\ldots,v_{2n+1}\right\\}$. For any
$m,n\in\mathbb{N}$, define the graph $K_{2n+1}^{\star m}$ as follows:

$V(K_{2n+1}^{\star m})=V(K_{2n+1})\cup\left\\{u,w_{1},\ldots,w_{m}\right\\}$,
$E(K_{2n+1}^{\star
m})=E(K_{2n+1})\cup\left\\{v_{1}u\right\\}\cup\left\\{uw_{i}\colon\,1\leq
i\leq m\right\\}$.

Clearly, $K_{2n+1}^{\star m}$ is a connected with $|V\left(K_{2n+1}^{\star
m}\right)|=m+2n+2$ and $\Delta\left(K_{2n+1}^{\star
m}\right)=\max\\{m+1,2n+1\\}$.

###### Theorem 37

If $n\geq 2$ and $m\geq 6n$, then $K_{2n+1}^{\star m}\notin\mathfrak{N}_{c}$.

  * Proof.

Suppose, to the contrary, that $K_{2n+1}^{\star m}$ has an interval cyclic
$t$-coloring $\alpha$ for some $t\geq d(u)=6n+1$.

Let $H=K_{2n+1}^{\star m}-w_{1}-w_{2}-\cdots-w_{m}$. Also, let
$C=\bigcup_{v\in V(H)}S(v,\alpha)$ and $\overline{C}=[1,t]\setminus C$. Since
$H$ is connected, it is not difficult to see that either $C$ or $\overline{C}$
is an interval of integers. Let $|C|=t^{\prime}$. Clearly, $t^{\prime}\leq t$.
Now let us consider the restriction of the coloring $\alpha$ on the edges of
the subgraph $H$ of $K_{2n+1}^{\star m}$. Let $\alpha_{H}$ be this edge-
coloring. By rotating of colors of $C$ along the cycle with colors
$1,\ldots,t$, we get a new edge-coloring $\alpha_{H}^{\prime}$ of $H$ with
colors $1,\ldots,t^{\prime}$. Since $\alpha$ is an interval cyclic
$t$-coloring of $K_{2n+1}^{\star m}$ and taking into account that the vertex
$u$ in $H$ is pendant, we obtain that $\alpha_{H}^{\prime}$ is an interval
cyclic $t^{\prime}$-coloring of $H$. Moreover, by Corollary 13, we have
$t^{\prime}\leq 3|V(H)|-6=3(2n+2)-6=6n$. Since $t\geq 6n+1$, we get that
$\alpha_{H}^{\prime}$ is also an interval $t^{\prime}$-coloring of $H$. In
[8], it was proved that $H\notin\mathfrak{N}$, so this contradiction proves
the theorem. $\square$

###### Corollary 38

For any integer $d\geq 13$, there exists a connected graph $G$ such that
$G\notin\mathfrak{N}_{c}$ and $\Delta(G)=d$.

Now we show that $K_{5}^{\star 11}\notin\mathfrak{N}_{c}$. Note that
$|V\left(K_{5}^{\star 11}\right)|=17$ and $\Delta\left(K_{5}^{\star
11}\right)=12$. Suppose that, to the contrary, that $K_{5}^{\star 11}$ has an
interval cyclic $t$-coloring $\alpha$ for some $t\geq 12$. Similarly as in the
proof of Theorem 37, we can consider the subgraph $H=K_{5}^{\star
11}-w_{1}-w_{2}-\cdots-w_{11}$ of $K_{5}^{\star 11}$. Let
$t^{\prime}=\left|\bigcup_{v\in V(H)}S(v,\alpha)\right|$ and $\alpha_{H}$ be
the restriction of the coloring $\alpha$ on the edges of the subgraph $H$ of
$K_{5}^{\star 11}$. Then, let $\alpha_{H}^{\prime}$ be the edge-coloring of
$H$ with colors $1,\ldots,t^{\prime}$. Since $\alpha$ is an interval cyclic
$t$-coloring of $K_{5}^{\star 11}$ and taking into account that the vertex $u$
in $H$ is pendant, it can be easily seen that $\alpha_{H}^{\prime}$ is an
interval cyclic $t^{\prime}$-coloring of $H$, where $t^{\prime}\leq t$.
Clearly, $t^{\prime}\leq|E(H)|=11$. Since $t\geq 12$, we obtain that
$\alpha_{H}^{\prime}$ is also an interval $t^{\prime}$-coloring of $H$, which
is a contradiction. From here, we get the following

###### Corollary 39

For any integer $d\geq 12$, there exists a connected graph $G$ such that
$G\notin\mathfrak{N}_{c}$ and $\Delta(G)=d$.

##  8 Problems and Conjectures

In this section we collected different problems and conjectures that arose in
previous sections. Our first conjectures concern the parameters $w_{c}(G)$ and
$W_{c}(G)$ of an interval cyclically colorable graph $G$. In section 3, we
proved that if $G$ is a connected triangle-free graph with at least two
vertices and $G\in\mathfrak{N}_{c}$, then $W_{c}(G)\leq|V(G)|+\Delta(G)-2$.
However, we think that the maximum degree in the upper bound can be omitted;
more precisely we believe that the following is true:

###### Conjecture 40

If $G$ is a connected triangle-free graph and $G\in\mathfrak{N}_{c}$, then
$W_{c}(G)\leq|V(G)|$.

Note that if Conjecture 40 is true, then this upper bound cannot be improved,
since $W_{c}(K_{m,n})\geq m+n$ ($\min\\{m,n\\}\geq 2$), by Corollary 30. We
also proved that if $G$ is a connected graph with at least two vertices and
$G\in\mathfrak{N}_{c}$, then $W_{c}(G)\leq 2|V(G)|+\Delta(G)-4$. We again
think that the maximum degree in this upper bound can be omitted; more
precisely we believe that the following is true:

###### Conjecture 41

If $G$ is a connected graph with at least two vertices and
$G\in\mathfrak{N}_{c}$, then $W_{c}(G)\leq 2|V(G)|-3$.

It is worth noting that there exists a connection between Conjecture 40 and
Conjecture 41. If one can prove that Conjecture 40 is true, then we able to
show that $W_{c}(G)\leq 2|V(G)|-1$ for an interval cyclically colorable
connected graph $G$.

It is known that all regular graphs $G$ are interval cyclically colorable and
$w_{c}(G)=\chi^{\prime}(G)$. Moreover, if $G$ is interval colorable, then $G$
is interval cyclically colorable and $w_{c}(G)=\chi^{\prime}(G)=\Delta(G)$. On
the other hand, in section 3, it was shown that there are many interval
cyclically colorable graphs $G$ for which $w_{c}(G)>\chi^{\prime}(G)$. So, it
is interesting to investigate the following

###### Problem 1

Characterize all interval cyclically colorable graphs $G$ for which
$w_{c}(G)=\chi^{\prime}(G)$.

In section 3, we also investigated the feasible sets of interval cyclically
colorable graphs. In particular, we proved that if $G$ is interval colorable,
then $\left[\Delta(G),W(G)\right]\subseteq F(G)$. On the other hand, we gave
some examples of interval cyclically graphs $G$ for which $F(G)$ is not gap-
free. So, it is interesting to investigate the following

###### Problem 2

Characterize all interval cyclically colorable graphs $G$ for which $F(G)$ is
gap-free.

For example, we know that if $T$ is a tree, then $F(T)$ is gap-free [14], but
we also strongly believe that for any $m,n\in\mathbb{N}$, $F(K_{2n})$,
$F(K_{m,n})$ and $F(Q_{n})$ are gap-free.

In sections 4 and 5, we investigated interval cyclic colorings of complete,
complete bipartite and tripartite graphs, but the following problems are still
open:

###### Problem 3

What is the exact value of $W_{c}\left(K_{n}\right)$ for any $n\in\mathbb{N}$?

###### Problem 4

What are the exact values of $w_{c}\left(K_{l,m,n}\right)$ and
$W_{c}\left(K_{m,n}\right)$, $W_{c}\left(K_{l,m,n}\right)$ for any
$l,m,n\in\mathbb{N}$?

In sections 4 and 5, we proved that all complete bipartite and tripartite
graphs are interval cyclically colorable, but we think that a more general
result is true:

###### Conjecture 42

All complete multipartite graphs are interval cyclically colorable.

In section 6, we investigated interval cyclic colorings of hypercubes $Q_{n}$
and proved that $W_{c}\left(Q_{n}\right)=O(n^{2})$, but the following problem
remains open:

###### Problem 5

What is the exact value of $W_{c}\left(Q_{n}\right)$ for any $n\in\mathbb{N}$?

In [23], Nadolski showed that if $G$ is a connected graph with $\Delta(G)=3$,
then $G\in\mathfrak{N}_{c}$ and $w_{c}(G)\leq 4$. From here and taking into
account that all simple paths and cycles are interval cyclically colorable, we
obtain that all subcubic graphs are interval cyclically colorable. On the
other hand, in section 7, we proved that for any integer $d\geq 12$, there
exists a connected graph $G$ such that $G\notin\mathfrak{N}_{c}$ and
$\Delta(G)=d$. So, it is naturally to consider the following

###### Problem 6

Is there a connected graph $G$ such that $4\leq\Delta(G)\leq 11$ and
$G\notin\mathfrak{N}_{c}$?

  * Acknowledgement

We would like to thank the organizers of 7-th Cracow conference on Graph
Theory “Rytro’ 14”for the nice environment and working atmosphere at the
conference.

## References

  * [1] A.S. Asratian, R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math. 5 (1987) 25-34 (in Russian).
  * [2] A.S. Asratian, R.R. Kamalian, Investigation on interval edge-colorings of graphs, J. Combin. Theory Ser. B 62 (1994) 34-43.
  * [3] A.S. Asratian, T.M.J. Denley, R. Haggkvist, Bipartite Graphs and their Applications, Cambridge University Press, Cambridge, 1998.
  * [4] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94.
  * [5] K. Giaro, M. Kubale, Consecutive edge-colorings of complete and incomplete Cartesian products of graphs, Congr, Numer. 128 (1997) 143-149.
  * [6] K. Giaro, M. Kubale, Compact scheduling of zero-one time operations in multi-stage systems, Discrete Appl. Math. 145 (2004) 95-103.
  * [7] K. Giaro, M. Kubale, M. Malafiejski, On the deficiency of bipartite graphs, Discrete Appl. Math. 94 (1999) 193-203.
  * [8] K. Giaro, M. Kubale, M. Malafiejski, Consecutive colorings of the edges of general graphs, Discrete Math. 236 (2001) 131-143.
  * [9] A. Grzesik, H. Khachatrian, Interval edge-colorings of $K_{1,m,n}$, Discrete Appl. Math. 174 (2014) 140-145.
  * [10] H.M. Hansen, Scheduling with minimum waiting periods, Master’s Thesis, Odense University, Odense, Denmark, 1992 (in Danish).
  * [11] D. Hanson, C.O.M. Loten, B. Toft, On interval colorings of bi-regular bipartite graphs, Ars Combin. 50 (1998) 23-32.
  * [12] R.R. Kamalian, Interval colorings of complete bipartite graphs and trees, preprint, Comp. Cen. of Acad. Sci. of Armenian SSR, Erevan, 1989 (in Russian).
  * [13] R.R. Kamalian, Interval edge colorings of graphs, Doctoral Thesis, Novosibirsk, 1990.
  * [14] R.R. Kamalian, On cyclically-interval edge colorings of trees, Buletinul of Academy of Sciences of the Republic of Moldova, Matematica 1(68) (2012) 50-58.
  * [15] R.R. Kamalian, On a number of colors in cyclically interval edge colorings of simple cycles, Open J. Discrete Math. 3 (2013) 43-48.
  * [16] R.R. Kamalian, A.N. Mirumian, Interval edge colorings of bipartite graphs of some class, Dokl. NAN RA, 97 (1997) 3-5 (in Russian).
  * [17] R.R. Kamalian, P.A. Petrosyan, Interval colorings of some regular graphs, Math. Probl. Comput. Sci. 25 (2006) 53-56.
  * [18] R.R. Kamalian, P.A. Petrosyan, A note on interval edge-colorings of graphs, Math. Probl. Comput. Sci. 36 (2012) 13-16.
  * [19] R.R. Kamalian, P.A. Petrosyan, A note on upper bounds for the maximum span in interval edge-colorings of graphs, Discrete Math. 312 (2012) 1393-1399.
  * [20] A. Kotzig, $1$-Factorizations of cartesian products of regular graphs, J. Graph Theory 3 (1979) 23-34.
  * [21] M. Kubale, Graph Colorings, American Mathematical Society, 2004.
  * [22] M. Kubale, A. Nadolski, Chromatic scheduling in a cyclic open shop, European J. Oper. Res. 164 (2005) 585-591.
  * [23] Nadolski, Compact cyclic edge-colorings of graphs, Discrete Math. 308 (2008) 2407-2417.
  * [24] P.A. Petrosyan, Interval edge-colorings of complete graphs and $n$-dimensional cubes, Discrete Math. 310 (2010) 1580-1587.
  * [25] P.A. Petrosyan, Interval edge colorings of some products of graphs, Discuss. Math. Graph Theory 31(2) (2011) 357-373.
  * [26] P.A. Petrosyan, H.H. Khachatrian, H.G. Tananyan, Interval edge-colorings of Cartesian products of graphs I, Discuss. Math. Graph Theory 33(3) (2013) 613-632.
  * [27] P.A. Petrosyan, H.H. Khachatrian, L.E. Yepremyan, H.G. Tananyan, Interval edge-colorings of graph products, in: Proceedings of the CSIT Conference (2011) 89-92.
  * [28] P.A. Petrosyan, H.H. Khachatrian, Interval non-edge-colorable bipartite graphs and multigraphs, J. Graph Theory 76 (2014) 200-216.
  * [29] S.V. Sevast’janov, Interval colorability of the edges of a bipartite graph, Metody Diskret. Analiza 50 (1990) 61-72 (in Russian).
  * [30] V.G. Vizing, On an estimate of the chromatic class of a $p$-graph, Disc. Analiz 3 (1964) 25-30 (in Russian).
  * [31] V.G. Vizing, The chromatic class of a multigraph, Kibernetika 3 (1965) 29-39 (in Russian).
  * [32] D. de Werra, Ph. Solot, Compact cylindrical chromatic scheduling, SIAM J. Disc. Math, Vol. 4, N4 (1991) 528-534.
  * [33] D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 2001.